NP-completeness of some edge-disjoint paths problems

DOI10.1016/0166-218X(93)E0177-ZzbMath0831.68078MaRDI QIDQ1897369

Jens Vygen

Publication date: 27 August 1995

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

zbMATH Keywords

NP-completenessedge-disjoint paths problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Eulerian and Hamiltonian graphs (05C45)

Related Items (24)

Eulerian disjoint paths problem in grid graphs is NP-complete ⋮ NP-completeness of some edge-disjoint paths problems ⋮ On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs ⋮ Combing a Linkage in an Annulus ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ Models for the single-vehicle preemptive pickup and delivery problem ⋮ Unnamed Item ⋮ Almost disjoint paths and separating by forbidden pairs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Finding disjoint paths in split graphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Tight Bounds for Linkages in Planar Graphs ⋮ Precoloring extension on unit interval graphs ⋮ Multiflows in symmetric digraphs ⋮ The edge-disjoint paths problem is NP-complete for series-parallel graphs ⋮ On structural parameterizations of the edge disjoint paths problem ⋮ Disjoint paths in symmetric digraphs ⋮ Unnamed Item ⋮ Euler Digraphs

Cites Work

• Unnamed Item
• Half-integral five-terminus flows
• Multicommodity flows in planar graphs
• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• A Minimax Theorem for Directed Graphs
• Feasibility of Two Commodity Network Flows
• Weak Three-Linking in Eulerian Dgraphs

This page was built for publication: NP-completeness of some edge-disjoint paths problems