General vertex disjoint paths in series-parallel graphs
type: Item
instance of: scholarly article
title: General vertex disjoint paths in series-parallel graphs
zbMATH Open document ID: 0786.05080
DOI: 10.1016/0166-218X(93)90035-M
author: Ephraim Korach
author: Ady Tal
published in: Discrete Applied Mathematics
publication date: 1993-05-16T00:00:00Z
review text: The vertex disjoint path problem is NP-complete even for planar graphs. Robertson and Seymour proved that this problem becomes polynomial when the number of paths is a fixed integer. A linear time algorithm for solving the decision version of the general problem when the input graph is a series-parallel graph is presented.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 166470
zbMATH Keywords: vertex disjoint path problem
zbMATH Keywords: NP-complete
zbMATH Keywords: planar graphs
zbMATH Keywords: linear time algorithm
zbMATH Keywords: series-parallel graph
reviewed by: Maciej M. Sysło
MaRDI profile type: Publication
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: Q3812222
cites work: Q5422499
cites work: Topology of series-parallel networks
cites work: The NP-completeness column: an ongoing guide
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Disjoint Paths—A Survey
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. VI. Disjoint paths across a disc
cites work: Q3972953
cites work: Disjoint paths in graphs
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: Q3343454
cites work: Linear-time computability of combinatorial problems on series-parallel graphs
cites work: 2-linked graphs
description: scientific article; zbMATH DE number 166470