网树求解有向无环图中具有长度约束的最大不相交路径

李艳; 武优西; 黄春萍; 张志颖; 曾珍香

doi:10.11959/j.issn.1000-436x.2015145

您当前的位置：

首页 >

文章列表页 >

网树求解有向无环图中具有长度约束的最大不相交路径

学术论文 | 更新时间：2024-06-05

- 网树求解有向无环图中具有长度约束的最大不相交路径
- Nettree for maximum disjoint paths with length constraint in DAG
- 通信学报 2015年36卷第8期页码：38-49
- 作者机构：
  
  1. 河北工业大学经济管理学院，天津 300401
  2. 河北工业大学计算机科学与软件学院，天津 300401
- 作者简介：
  
  [ "李艳（1975-），女，河北香河人，博士，河北工业大学副教授，主要研究方向为供应链管理与数据挖掘。" ]
  [ "武优西（1974-），男，河北故城人，博士，河北工业大学教授，主要研究方向为数据挖掘与智能计算。" ]
  [ "黄春萍（1976-），女，河北抚宁人，博士，河北工业大学副教授，主要研究方向为创业管理及其复杂性。" ]
  [ "张志颖（1976-），女，河北遵化人，博士，河北工业大学副教授，主要研究方向为信息系统与组织合作。" ]
  [ "曾珍香（1965-），女，湖南益阳人，河北工业大学教授、博士生导师，主要研究方向为企业信息资源规划。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61370144);国家社会科学基金资助项目(12CGL112);河北省自然科学基金资助项目(F2013202138);河北省自然科学基金资助项目(G2012202068);河北省教育厅重点基金资助项目(ZH2012038);河北省科技支撑计划基金资助项目(14210102D)
- DOI：10.11959/j.issn.1000-436x.2015145
  中图分类号： TP301
- 网络出版日期：2015-08，
  
  纸质出版日期：2015-08-25
- 稿件说明：
移动端阅览
李艳, 武优西, 黄春萍, 等. 网树求解有向无环图中具有长度约束的最大不相交路径[J]. 通信学报, 2015,36(8):38-49.

Yan LI, You-xi WU, Chun-ping HUANG, et al. Nettree for maximum disjoint paths with length constraint in DAG[J]. Journal on communications, 2015, 36(8): 38-49.
李艳, 武优西, 黄春萍, 等. 网树求解有向无环图中具有长度约束的最大不相交路径[J]. 通信学报, 2015,36(8):38-49. DOI： 10.11959/j.issn.1000-436x.2015145.

Yan LI, You-xi WU, Chun-ping HUANG, et al. Nettree for maximum disjoint paths with length constraint in DAG[J]. Journal on communications, 2015, 36(8): 38-49. DOI： 10.11959/j.issn.1000-436x.2015145.

摘要

对有向无环图中具有长度约束的最大不相交路径问题进行研究，该问题是求解图中两点间路径长度为 k的最大不相交路径。为了对该问题进行求解，提出了贪婪搜索算法(GP

greedy path)，该算法先将一个有向无环图转化为一棵深度为k+1的网树，然后计算每个网树节点的树根叶子路径数，并以此计算图中每个顶点的总路径数，之后从网树的第k+1层节点出发，在当前节点的双亲节点中选择未被使用且总路径数最小的双亲，以此形成一条优化的不相交路径，最后迭代这一过程，直到不再有新的不相交路径为止。GP 算法的时间和空间复杂度分别为O(wkn(p+q))和O(kn(p+q)+n

)。为了测试GP算法的近似性，又建立了一种能够生成人工数据的算法，该算法能够准确地控制有向无环图中最大不相交路径的数量。通过该算法生成了大量测试用数据，实验结果表明GP算法较其他对比性算法具有良好的近似性且实际求解时间较短，验证了该方法的有效性和可行性。

Abstract

The problem of the maximum disjoint paths in directed acyclic graphs(DAG)was researched which is to find the maximum disjoint paths with length k between two given vertices.A greedy algorithm named greedy path(GP)was proposed to solve the problem.GP transformed a DAG into a nettree with depth k+1 at first.Then the number of root-leaf paths for each node of the nettree was calculated to achieve the number of total paths for each vertex of the DAG.In order to obtain an optimized disjoint path

GP selected the node in the(k+1)th level of the nettree as the current node

and searched for the optimized parent in the usable parents whose number of total paths was minimal.This process was iterated

until there was no disjoint path.The space and time complexities of GP are O(wkn(p+q))and O(kn(p+q)+n

).To evaluate the performance of GP

an algorithm which can create artificial DAG with known maximum disjoint paths was also proposed.Experimental results show that GP can get better performance than other competitive algorithms.

关键词

Keywords

references

KUMAR A , VARMA S . Geographic node-disjoint path routing for wireless sensor networks [J ] . Sensors Journal,IEEE , 2010 , 10 ( 6 ): 1138 - 1139 .

方效林 , 石胜飞 , 李建中 . 无线传感器网络一种不相交路径路由算法 [J ] . 计算机研究与发展 , 2009 , 46 ( 12 ): 2053 - 2061 .

FANG X L , SHI S F , LI J Z . A disjoint multi-path routing algorithm in wireless sensor network [J ] . Journal of Computer Research and Development , 2009 , 46 ( 12 ): 2053 - 2061 .

HASHIGUCHI T,TAJIMA K , TAKITA Y , NAITO T . Node-disjoint paths search in WDM networks with asymmetric nodes [A ] . 2011 15th IEEE International Conference on Optical Network Design and Modeling(ONDM) [C ] . 2011 . 1 - 6 .

包学才 , 戴伏生 , 韩卫占 . 基于拓扑的不相交路径抗毁性评估方法 [J ] . 系统工程与电子技术 , 2012 , 34 ( 1 ): 168 - 174 .

BAO X C , DAI F S , HAN W Z . Evaluation method of network invulnerability based on disjoint paths in topology [J ] . Systems Engineering and Electronics , 2012 , 34 ( 1 ): 168 - 174 .

GORBENKO A , POPOV V . The problem of finding two edge-disjoint hamiltonian cycles [J ] . Applied Mathematical Sciences , 2012 , 132 ( 6 ): 6563 - 6566 .

CYGAN M,MARX D , PILIPCZUK M , PILIPCZUK M . The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable [A ] . Foundations of Computer Science(FOCS),2013 IEEE 54th Annual Symposium [C ] .IEEE, 2013 . 197 - 206 .

ITAI A , PERL Y , SHILOACH Y . The complexity of finding maximum disjoint paths with length constraints [J ] . Networks , 1982 , 12 ( 3 ): 277 - 286 .

SEGUIN-CHARBONNEAU L , SHEPHERD F B . Maximum edgedisjoint paths in planar graphs with congestion 2 [A ] . Foundations of Computer Science(FOCS),2011 IEEE 52nd Annual Symposium [C ] .IEEE, 2011 . 200 - 209 .

GUO L , SHEN H . On the complexity of the edge-disjoint min-min problem in planar digraphs [J ] . Theoretical Computer Science , 2012 , 432 : 58 - 63 .

CHEN X B . Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs [J ] . Information Processing Letters , 2010 , 110 ( 6 ): 203 - 205 .

YU C C , LIN C H , WANG B F . Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax k vertex-disjoint paths in a directed acyclic graph [J ] . Journal of Computer and System Sciences , 2010 , 76 ( 8 ): 697 - 708 .

冯涛 , 郭显 , 马建峰 , 等 . 可证明安全的节点不相交多路径源路由协议 [J ] . 软件学报 , 2010 , 21 ( 7 ): 1717 - 1731 .

FENG T , GUO X , MA J F , et al . Provably secure approach for multiple node-disjoint paths source routing protocol [J ] . Journal of Software , 2010 , 21 ( 7 ): 1717 - 1731 .

WU B Y . A note on approximating the min-max vertex disjoint paths on directed acyclic graphs [J ] . Journal of Computer and System Sciences , 2011 , 77 ( 6 ): 1054 - 1057 .

WU Y,WU X , MIN F , LI Y . A nettree for pattern matching with flexible wildcard constraints [A ] . Proceedings of the 2010 IEEE International Conference on Information Reuse and Integration [C ] . Las Vegas,USA , 2010 . 109 - 114 .

李艳 , 孙乐 , 朱怀忠 , 等 . 网树求解有向无环图中具有长度约束的简单路径和最长路径问题 [J ] . 计算机学报 , 2012 , 35 ( 10 ): 2194 - 2203 .

LI Y , SUN L , ZHU H , et al . A nettree for simple paths with length constraint and the longest path in directed acyclic graphs [J ] . Chinese Journal of Computers , 2012 , 35 ( 10 ): 2194 - 2203 .

浏览量

1238

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据