The edge-disjoint paths problem is NP-complete for series-parallel graphs

DOI10.1016/S0166-218X(01)00223-2zbMath1001.68091MaRDI QIDQ5954246

Xiao Zhou, Jens Vygen, Takao Nishizeki

Publication date: 22 April 2002

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

zbMATH Keywords

series-parallel graphssubgraph isomorphism problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items

Edge-disjoint odd cycles in 4-edge-connected graphs ⋮ Call control with \(k\) rejections ⋮ As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ A tight relation between series-parallel graphs and bipartite distance hereditary graphs ⋮ The minimum vulnerability problem on specific graph classes ⋮ The power of cut-based parameters for computing edge-disjoint paths ⋮ On maximum common subgraph problems in series-parallel graphs ⋮ The disjoint path cover in the data center network HSDC with prescribed vertices in each path ⋮ Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ Online interval scheduling with predictions ⋮ Line graphs of bounded clique-width ⋮ Finding disjoint paths in split graphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs ⋮ The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs ⋮ Disjoint paths in sparse graphs ⋮ List total colorings of series-parallel graphs ⋮ Multiflows in symmetric digraphs ⋮ Max-multiflow/min-multicut for G+H series-parallel ⋮ Vertex disjoint paths on clique-width bounded graphs ⋮ New algorithms for maximum disjoint paths based on tree-likeness ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Disjoint paths in symmetric digraphs ⋮ Walking through waypoints ⋮ Complexity results for minimum sum edge coloring ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of subgraph isomorphism for classes of partial k-trees
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Edge-disjoint paths in a grid bounded by two nested rectangles
• Edge-disjoint paths in planar graphs
• Algorithms for multicommodity flows in planar graphs
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Some simplified NP-complete graph problems
• Approximations for the disjoint paths problem in high-diameter planar networks
• Graph minors. IX: Disjoint crossed paths
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Graph minors. XIII: The disjoint paths problem
• NP-completeness of some edge-disjoint paths problems
• Finding edge-disjoint paths in partial \(k\)-trees
• On the complexity of the disjoint paths problem
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks
• Edge-Coloring Partialk-Trees
• Linear-time computability of combinatorial problems on series-parallel graphs
• An algebraic theory of graph reduction
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Faster algorithms for subgraph isomorphism of κ-connected partial κ-trees