The complexity of finding two disjoint paths with min-max objective function
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 105-115 |
Journal / Publication | Discrete Applied Mathematics |
Volume | 26 |
Issue number | 1 |
Publication status | Published - Jan 1990 |
Externally published | Yes |
Link(s)
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.
Bibliographic 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].
Citation Format(s)
The complexity of finding two disjoint paths with min-max objective function. / Li, Chung-Lun; McCormick, S.Thomas; Simchi-Levi, David.
In: Discrete Applied Mathematics, Vol. 26, No. 1, 01.1990, p. 105-115.
In: Discrete Applied Mathematics, Vol. 26, No. 1, 01.1990, p. 105-115.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review