The complexity of finding two disjoint paths with min-max objective function

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

doi:10.1016/0166-218X(90)90024-7

The complexity of finding two disjoint paths with min-max objective function

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

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

133 Citations (Scopus)

Abstract

Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. 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 as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case. © 1990.

Original language	English
Pages (from-to)	105-115
Journal	Discrete Applied Mathematics
Volume	26
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(90)90024-7
Publication status	Published - Jan 1990
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.1016/0166-218X(90)90024-7Licence: Elsevier user license

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{345fa1028686491c98fddf4b78228f9f,

title = "The complexity of finding two disjoint paths with min-max objective function",

abstract = "Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. 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 as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case. {\textcopyright} 1990.",

author = "Chung-Lun Li and S.Thomas McCormick 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 = "1990",

month = jan,

doi = "10.1016/0166-218X(90)90024-7",

language = "English",

volume = "26",

pages = "105--115",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - The complexity of finding two disjoint paths with min-max objective function

AU - Li, Chung-Lun

AU - McCormick, S.Thomas

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 - 1990/1

Y1 - 1990/1

N2 - Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. 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 as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case. © 1990.

AB - Given a network G = (V,E) and two vertices s and t, we consider the problem of finding two disjoint paths from s to t such that the length of the longer path is minimized. 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 as well as some related problems are strongly NP-complete. We also give a pseudo-polynomial-time algorithm for the acyclic directed case. © 1990.

UR - http://www.scopus.com/inward/record.url?scp=0041061428&partnerID=8YFLogxK

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

U2 - 10.1016/0166-218X(90)90024-7

DO - 10.1016/0166-218X(90)90024-7

M3 - RGC 21 - Publication in refereed journal

SN - 0166-218X

VL - 26

SP - 105

EP - 115

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1

ER -

The complexity of finding two disjoint paths with min-max objective function

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this