GRAPH MINERS .13. THE DISJOINT PATHS PROBLEM

Authors
ROBERTSON N SEYMOUR PD
Citation
N. Robertson et Pd. Seymour, GRAPH MINERS .13. THE DISJOINT PATHS PROBLEM, J COMB TH B, 63(1), 1995, pp. 65-110
Citations number
29
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN journal
00958956 → ACNP
Volume
63
Issue
1
Year of publication
1995
Pages
65 - 110
Database
ISI
SICI code
0095-8956(1995)63:1<65:GM.TDP>2.0.ZU;2-2
Abstract
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.