NP-COMPLETENESS OF SOME EDGE-DISJOINT PATHS PROBLEMS

被引：49

作者：

VYGEN, J

机构：

[1] Institut für Ökonometrie und OR, Universität Bonn, D-53113 Bonn

来源：

DISCRETE APPLIED MATHEMATICS | 1995年 / 61卷 / 01期

关键词：

D O I：

10.1016/0166-218X(93)E0177-Z

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove: The directed edge-disjoint paths problem is NP-complete, even if (a) the underlying graph G is acyclic, the demand graph H consists just of three sets of parallel edges and G + H is Eulerian, or (b) G + H is planar, or (c) G is planar and acyclic. (d) The undirected edge-disjoint paths problem is NP-complete, even if G + H is Eulerian and H consists just of three sets of parallel edges.

引用

页码：83 / 90

页数：8

共 10 条

[1]

EVEN S, 1976, SIAM J COMPTNG, V5, P691

[2] WEAK 3-LINKING IN EULERIAN DIGRAPHS [J].