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.
|Number of pages||11|
|Journal||Discrete Applied Mathematics|
|Publication status||Published - 1 Jan 1990|
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics