AbstractWe consider the following problem: Given an integer K and a network G with two distinct vertices s and t, find a maximum number of vertex disjoint paths from s to t of length bounded by k. In a recent work [IPS] it was shown that for length greater that four this problem is NP-Hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorithm.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
