Finding disjoint paths with different path‐costs: Complexity and algorithms

Chung Lun Li, S. Thomas McCormick, David Simchi‐Levi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

69 Citations (Scopus)

Abstract

Consider a network G = V,E with distinguished vertices s and t, and with k different costs on every edge. We consider the problem of finding k disjoint paths from s to t such that the total cost of the paths is minimized, where the jth edge‐cost is associated with the jth path. The problem has several variants: The paths may be vertex‐disjoint or arc‐disjoint and the network may be directed or undirected. We show that all four versions of the problem are strongly NP‐complete even for k = 2. We describe polynomial time heuristics for the problem and a polynomial time algorithm for the acyclic directed case.
Original languageEnglish
Pages (from-to)653-667
Number of pages15
JournalNetworks
Volume22
Issue number7
DOIs
Publication statusPublished - 1 Jan 1992
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications

Cite this