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

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

doi:10.1002/net.3230220705

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

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

^*Corresponding author for this work

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

72 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. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

Original language	English
Pages (from-to)	653-667
Journal	Networks
Volume	22
Issue number	7
DOIs	https://doi.org/10.1002/net.3230220705
Publication status	Published - Dec 1992
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1002/net.3230220705

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{034228387c18437e953cf3c91901ce6d,

title = "Finding disjoint paths with different path‐costs: Complexity and algorithms",

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. Copyright {\textcopyright} 1992 Wiley Periodicals, Inc., A Wiley Company",

author = "Chung‐Lun Li and \{Thomas McCormick\}, S. and David Simchi‐Levi",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1992",

month = dec,

doi = "10.1002/net.3230220705",

language = "English",

volume = "22",

pages = "653--667",

journal = "Networks",

issn = "0028-3045",

publisher = "Wiley-Liss Inc.",

number = "7",

}

TY - JOUR

T1 - Finding disjoint paths with different path‐costs

T2 - Complexity and algorithms

AU - Li, Chung‐Lun

AU - Thomas McCormick, S.

AU - Simchi‐Levi, David

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1992/12

Y1 - 1992/12

N2 - 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. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

AB - 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. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

UR - https://www.scopus.com/pages/publications/85013990412

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85013990412&origin=recordpage

U2 - 10.1002/net.3230220705

DO - 10.1002/net.3230220705

M3 - RGC 21 - Publication in refereed journal

SN - 0028-3045

VL - 22

SP - 653

EP - 667

JO - Networks

JF - Networks

IS - 7

ER -

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

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this