General vertex disjoint paths in series-parallel graphs

DOI10.1016/0166-218X(93)90035-MzbMath0786.05080MaRDI QIDQ1208474

Ephraim Korach, Ady Tal

Publication date: 16 May 1993

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

planar graphslinear time algorithmNP-completeseries-parallel graphvertex disjoint path problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Improved algorithms for finding length-bounded two vertex-disjoint paths in a planar graph and minmax \(k\) vertex-disjoint paths in a directed acyclic graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. VI. Disjoint paths across a disc
• Disjoint paths in graphs
• 2-linked graphs
• Topology of series-parallel networks
• Disjoint Paths—A Survey
• The NP-completeness column: an ongoing guide
• Graph minors. II. Algorithmic aspects of tree-width
• A Polynomial Solution to the Undirected Two Paths Problem
• Linear-time computability of combinatorial problems on series-parallel graphs
• On the Computational Complexity of Combinatorial Problems