GRAPH MINERS .13. THE DISJOINT PATHS PROBLEM

被引：741

作者：

ROBERTSON, N ^{[1
]}

SEYMOUR, PD ^{[1
]}

机构：

[1] BELLCORE, MORRISTOWN, NJ 07960 USA

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1995年 / 63卷 / 01期

关键词：

D O I：

10.1006/jctb.1995.1006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We describe an algorithm, which for fixed k greater than or equal to 0 has running time O(/V(G)/(3)), to solve the following problem: given a graph G and k pairs of vertices of G, decide if there are k mutually vertex-disjoint paths of G joining the pairs. (C) 1995 Academic Press, Inc.

引用

页码：65 / 110

页数：46

共 29 条

[1] LINEAR TIME ALGORITHMS FOR NP-HARD PROBLEMS RESTRICTED TO PARTIAL K-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (01) :11-24

[2] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[3]

BODLAENDER H, 1993, UNPUB LINEAR TIME AL

[4]

FILOTTI IS, 1979, 11TH P ANN ACM S THE, P27

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

FORTUNE, S ;

HOPCROFT, J ;

WYLLIE, J .

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

[6]

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

[7] GENERALIZATION OF N-FOLD RELATIONSHIP FOR GRAPHS [J].

JUNG, HA .

MATHEMATISCHE ANNALEN, 1970, 187 (02) :95-+

[8]

Karp R. M., 1975, Networks, V5, P45

[9]

KELMANS AK, 1981, C MATH SOC JANOS BOL, V37, P487

[10]

LARMAN DG, 1970, P LOND MATH SOC, V20, P144

← 1 2 3 →