THE COMPLEXITY OF FINDING 2 DISJOINT PATHS WITH MIN-MAX OBJECTIVE FUNCTION

被引：104

作者：

LI, CL

MCCORMICK, ST

SIMCHILEVI, D

机构：

[1] Department of Industrial Engineering and Operation Research, Columbia University, New York

来源：

DISCRETE APPLIED MATHEMATICS | 1990年 / 26卷 / 01期

基金：

美国国家科学基金会;

关键词：

D O I：

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

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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.

引用

页码：105 / 115

页数：11

共 10 条

[1]

Even S., 1976, SIAM Journal on Computing, V5, P691, DOI 10.1137/0205048

[2] THE DIRECTED SUBGRAPH HOMEOMORPHISM PROBLEM [J].

FORTUNE, S ;

HOPCROFT, J ;

WYLLIE, J .

THEORETICAL COMPUTER SCIENCE, 1980, 10 (02) :111-121

[3]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[4]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[5]

Harary Frank, 1972, GRAPH THEORY

[6] THE COMPLEXITY OF FINDING MAXIMUM DISJOINT PATHS WITH LENGTH CONSTRAINTS [J].

ITAI, A ;

PERL, Y ;

SHILOACH, Y .

NETWORKS, 1982, 12 (03) :277-286

[7]

LI CL, THESIS COLUMBIA U NE

[8]

PERL Y, 1978, J ACM, V25, P1, DOI 10.1145/322047.322048

[9]

Suurballe J. W., 1974, Networks, V4, P125, DOI 10.1002/net.3230040204

[10] A QUICK METHOD FOR FINDING SHORTEST PAIRS OF DISJOINT PATHS [J].

SUURBALLE, JW ;

TARJAN, RE .

NETWORKS, 1984, 14 (02) :325-336

← 1 →