Nettree for maximum disjoint paths with length constraint in DAG

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)+n2).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

• directed acyclic graph;length constraint;disjoint path;nettree