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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

129 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)105-115
Journal / PublicationDiscrete Applied Mathematics
Volume26
Issue number1
Publication statusPublished - Jan 1990
Externally publishedYes

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.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review