Heuristics for finding a maximum number of disjoint bounded paths

D. Ronen, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

25 Scopus citations

Abstract

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
JournalNetworks
Volume14
Issue number4
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

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

Cite this