General vertex disjoint paths in series-parallel graphs

DOI10.1016/0166-218X(93)90035-MMaRDI QIDQ1208474zbMATH OpenFDO

Authors Ephraim Korach, Ady Tal

Publication date 16 May 1993

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

zbMATH Keywords

NP-completeplanar graphslinear time algorithmseries-parallel graphvertex disjoint path problem

Mathematics Subject Classification ID

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

Recommendations

• Graph minors. XIII: The disjoint paths problem
• The Induced Disjoint Paths Problem
• Publication:3211338
• On the complexity of the disjoint paths problem
• scientific article; zbMATH DE number 437535

Cites work

• scientific article; zbMATH DE number 3878376 (Why is no real title available?)
• scientific article; zbMATH DE number 4081531 (Why is no real title available?)
• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Disjoint Paths—A Survey
• Disjoint paths in graphs
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. VI. Disjoint paths across a disc
• Graph theory
• Linear-time computability of combinatorial problems on series-parallel graphs
• On the Computational Complexity of Combinatorial Problems
• The NP-completeness column: an ongoing guide
• Topology of series-parallel networks

Cited in

(7)

• 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
• Vertex disjoint paths on clique-width bounded graphs
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Finding k Disjoint Paths in a Directed Planar Graph
• Measuring the distance to series-parallelity by path expressions
• Selecting vertex disjoint paths in plane graphs
• Vertex disjoint paths for dispatching in railways

This page was built for publication: General vertex disjoint paths in series-parallel graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1208474)