General vertex disjoint paths in series-parallel graphs (Q1208474): Difference between revisions

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.

0 references

Mathematics Subject Classification ID

05C85

0 references

0 references

0 references

0 references

0 references

vertex disjoint path problem

0 references

NP-complete

0 references

planar graphs

0 references

linear time algorithm

0 references

series-parallel graph

0 references

reviewed by

Maciej M. Sysło

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey

0 references

Q3812222

0 references

Q5422499

0 references

Topology of series-parallel networks

0 references

The NP-completeness column: an ongoing guide

0 references

On the Computational Complexity of Combinatorial Problems

0 references

Disjoint Paths—A Survey

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Graph minors. VI. Disjoint paths across a disc

0 references

Q3972953

0 references

Disjoint paths in graphs

0 references

A Polynomial Solution to the Undirected Two Paths Problem

0 references

Q3343454

0 references

Linear-time computability of combinatorial problems on series-parallel graphs

0 references

2-linked graphs

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1208474

@@ Property / reviewed by @@
-Maciej M. Sysło
@@ Property / reviewed by: Maciej M. Sysło / rank @@
-Normal rank
@@ Property / reviewed by @@
+Maciej M. Sysło
@@ Property / reviewed by: Maciej M. Sysło / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
+Normal rank
@@ Property / cites work @@
+Q3812222
@@ Property / cites work: Q3812222 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5422499
@@ Property / cites work: Q5422499 / rank @@
+Normal rank
@@ Property / cites work @@
+Topology of series-parallel networks
@@ Property / cites work: Topology of series-parallel networks / rank @@
+Normal rank
@@ Property / cites work @@
+The NP-completeness column: an ongoing guide
@@ Property / cites work: The NP-completeness column: an ongoing guide / rank @@
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Combinatorial Problems
+Normal rank
@@ Property / cites work @@
+Disjoint Paths—A Survey
@@ Property / cites work: Disjoint Paths—A Survey / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Graph minors. VI. Disjoint paths across a disc
@@ Property / cites work: Graph minors. VI. Disjoint paths across a disc / rank @@
+Normal rank
@@ Property / cites work @@
+Q3972953
@@ Property / cites work: Q3972953 / rank @@
+Normal rank
@@ Property / cites work @@
+Disjoint paths in graphs
@@ Property / cites work: Disjoint paths in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A Polynomial Solution to the Undirected Two Paths Problem
+Normal rank
@@ Property / cites work @@
+Q3343454
@@ Property / cites work: Q3343454 / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-time computability of combinatorial problems on series-parallel graphs
+Normal rank
@@ Property / cites work @@
+-linked graphs
@@ Property / cites work: 2-linked graphs / rank @@
+Normal rank