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 article publication › Journal article › Academic research › 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.

Original language	English
Pages (from-to)	105-115
Number of pages	11
Journal	Discrete Applied Mathematics
Volume	26
Issue number	1
DOIs	https://doi.org/10.1016/0166-218X(90)90024-7
Publication status	Published - 1 Jan 1990
Externally published	Yes

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

More information

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

Cite this

@article{c06c0cce535342eeab0908ebeaffa68a,

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.",

author = "Li, \{Chung Lun\} and McCormick, \{S. Thomas\} and David Simchi-Levi",

year = "1990",

month = jan,

day = "1",

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

PY - 1990/1/1

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

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.

UR - https://www.scopus.com/pages/publications/0041061428

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

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

M3 - Journal article

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

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this