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

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

Abstract

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.

Key words: directed acyclic graph, length constraint, disjoint path, nettree

Yan LI,You-xi WU,Chun-ping HUANG,Zhi-ying ZHANG,Zhen-xiang ZENG. Nettree for maximum disjoint paths with length constraint in DAG[J]. Journal on Communications, 2015, 36(8): 38-49.

Figures/Tables 16

References 15

[1]	KUMAR A , VARMA S . Geographic node-disjoint path routing for wireless sensor networks[J]. Sensors Journal,IEEE, 2010,10(6): 1138-1139.
[2]	方效林, 石胜飞, 李建中 . 无线传感器网络一种不相交路径路由算法[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.
[3]	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.
[4]	包学才, 戴伏生, 韩卫占 . 基于拓扑的不相交路径抗毁性评估方法[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.
[5]	GORBENKO A , POPOV V . The problem of finding two edge-disjoint hamiltonian cycles[J]. Applied Mathematical Sciences, 2012,132(6): 6563-6566.
[6]	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.
[7]	ITAI A , PERL Y , SHILOACH Y . The complexity of finding maximum disjoint paths with length constraints[J]. Networks, 1982,12(3): 277-286.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	冯涛, 郭显, 马建峰 ,等. 可证明安全的节点不相交多路径源路由协议[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.
[13]	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.
[14]	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.
[15]	李艳, 孙乐, 朱怀忠 ,等. 网树求解有向无环图中具有长度约束的简单路径和最长路径问题[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.

Metrics

Recommended 0

No Suggested Reading articles found!

d	k=5	k=6	k=7
0.06	36	30	27
0.08	41	30	24
0.1	44	34	26
0.12	36	30	25
0.14	44	35	28
0.16	39	32	28
0.18	44	29	28
0.2	42	35	29
0.25	35	28	32
0.3	39	29	28
0.35	40	31	27
0.4	43	29	29
0.45	42	30	26
0.5	42	28	28
0.55	40	31	29
0.6	43	32	28

d	LP	RP	SP	GP
0.06	27	29	33	33
0.08	32	30	36	39
0.1	34	36	41	42
0.12	32	32	36	36
0.14	36	36	43	43
0.16	34	37	39	39
0.18	35	37	43	44
0.2	38	35	39	40
0.25	31	34	35	35
0.3	36	35	37	37
0.35	39	38	40	40
0.4	40	37	42	42
0.45	38	40	41	41
0.5	39	42	41	41
0.55	40	39	40	40
0.6	42	38	43	43

d	LP	RP	SP	GP
0.06	20	20	24	23
0.08	19	19	24	24
0.1	20	19	25	25
0.12	20	19	24	25
0.14	21	22	27	27
0.16	23	21	27	26
0.18	24	21	27	27
0.2	23	25	28	28
0.25	28	25	31	31
0.3	23	23	27	27
0.35	25	26	27	27
0.4	27	27	28	28
0.45	24	24	25	25
0.5	26	27	28	28
0.55	28	27	28	28
0.6	26	26	27	28

算法		k=5			k=6			k=7			全部
算法	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60
LP	82.2%		94.1%	78.8%		95.0%	79.1%		91.2%	80.3%		93.5%
RP	83.4%		93.5%	80.4%		95.4%	77.2%		90.3%	80.8%		93.2%
SP	95.1%		98.5%	95.7%		100.0%	95.8%		97.4%	95.5%		98.6%
GP	96.9%		98.5%	95.3%		100.0%	95.3%		97.8%	96.0%		98.7%

算法		k=5			k=6			k=7			全部
算法	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60	d=0.06～0.20		d=0.25～0.60
LP	13.3		20.5	15.6		24.4	20.1		28.9	16.3		20.5
RP	13.9		20.1	16.2		24.6	19.0		29.1	16.3		20.5
SP	46.3		103.9	53.3		110.9	55.5		124.2	51.7		82.4
GP	17.4		34.0	20.8		36.5	25.8		41.4	21.3		29.3

Nettree for maximum disjoint paths with length constraint in DAG

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 16

References 15

Related Articles 2

Metrics

Recommended 0

[1]	Ke-jia ZHANG,Hong GAO. Incremental algorithm for finding disjoint paths in sensor networks [J]. Journal on Communications, 2010, 31(9A): 59-67.
[2]	Pin ZHANG,Jian-wu ZHANG,Le-min LI,Sheng ,WANG. Researches on the problem of link disjoint paths pair with QoS constraints [J]. Journal on Communications, 2006, 27(6): 36-42.