Finding k Disjoint Paths in a Directed Planar Graph
Author:
- Alexander SchrijverASAlexander Schrijver
- 1 August 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (4) , 780-788
Abstract
It is shown that, for each fixed k, the problem of finding k pairwise vertex-disjoint directed paths between given pairs of terminals in a directed planar graph is solvable in polynomial time.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Graph Minors .XIII. The Disjoint Paths ProblemJournal of Combinatorial Theory, Series B, 1995
- Finding disjoint trees in planar graphs in linear time1993
- Disjoint homotopic paths and trees in a planar graphDiscrete & Computational Geometry, 1991
- The directed subgraph homeomorphism problemTheoretical Computer Science, 1980
- The equivalence of theorem proving and the interconnection problemACM SIGDA Newsletter, 1975