The edge-disjoint paths problem is NP-complete for series-parallel graphs
From MaRDI portal
Publication:5954246
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)
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
