Heuristics for finding a maximum number of disjoint bounded paths

We 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 [9] it was shown that for length greater than 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.