Nettree for maximum disjoint paths with length constraint in DAG
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...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2015-08-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015145/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841539652523130880 |
|---|---|
| author | Yan LI You-xi WU Chun-ping HUANG Zhi-ying ZHANG Zhen-xiang ZENG |
| author_facet | Yan LI You-xi WU Chun-ping HUANG Zhi-ying ZHANG Zhen-xiang ZENG |
| author_sort | Yan LI |
| collection | DOAJ |
| description | 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<sup>2</sup>).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. |
| format | Article |
| id | doaj-art-560170c0e88641d6970e3bd1fae46958 |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2015-08-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-560170c0e88641d6970e3bd1fae469582025-01-14T06:53:18ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2015-08-0136384959694742Nettree for maximum disjoint paths with length constraint in DAGYan LIYou-xi WUChun-ping HUANGZhi-ying ZHANGZhen-xiang ZENGThe 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<sup>2</sup>).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.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015145/directed acyclic graphlength constraintdisjoint pathnettree |
| spellingShingle | Yan LI You-xi WU Chun-ping HUANG Zhi-ying ZHANG Zhen-xiang ZENG Nettree for maximum disjoint paths with length constraint in DAG Tongxin xuebao directed acyclic graph length constraint disjoint path nettree |
| title | Nettree for maximum disjoint paths with length constraint in DAG |
| title_full | Nettree for maximum disjoint paths with length constraint in DAG |
| title_fullStr | Nettree for maximum disjoint paths with length constraint in DAG |
| title_full_unstemmed | Nettree for maximum disjoint paths with length constraint in DAG |
| title_short | Nettree for maximum disjoint paths with length constraint in DAG |
| title_sort | nettree for maximum disjoint paths with length constraint in dag |
| topic | directed acyclic graph length constraint disjoint path nettree |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2015145/ |
| work_keys_str_mv | AT yanli nettreeformaximumdisjointpathswithlengthconstraintindag AT youxiwu nettreeformaximumdisjointpathswithlengthconstraintindag AT chunpinghuang nettreeformaximumdisjointpathswithlengthconstraintindag AT zhiyingzhang nettreeformaximumdisjointpathswithlengthconstraintindag AT zhenxiangzeng nettreeformaximumdisjointpathswithlengthconstraintindag |