Heuristics for finding a maximum number of disjoint bounded paths

D. Ronen, Y. Perl

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)531-544
Number of pages14
Issue number4
StatePublished - 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Heuristics for finding a maximum number of disjoint bounded paths'. Together they form a unique fingerprint.

Cite this