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

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

116 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.
Original languageEnglish
Pages (from-to)105-115
Number of pages11
JournalDiscrete Applied Mathematics
Volume26
Issue number1
DOIs
Publication statusPublished - 1 Jan 1990
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this