Eulerian disjoint paths problem in grid graphs is NP-complete

DOI10.1016/j.dam.2003.12.003zbMath1053.05078OpenAlexW2010748366MaRDI QIDQ1887070

Dániel Marx

Publication date: 23 November 2004

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

Full work available at URL: https://doi.org/10.1016/j.dam.2003.12.003

zbMATH Keywords

NP-completenessGridsDisjoint paths

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)

Related Items (10)

Hamiltonian cycles in linear-convex supergrid graphs ⋮ The shortest multipaths problem in a capacitated dense channel ⋮ Solving the edge‐disjoint paths problem using a two‐stage method ⋮ Multiflow Feasibility: An Annotated Tableau ⋮ Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs ⋮ The Hamiltonian properties of supergrid graphs ⋮ Finding edge-disjoint paths in networks: an ant colony optimization algorithm ⋮ Disjoint paths in sparse graphs ⋮ Precoloring extension on unit interval graphs ⋮ Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs

Cites Work

• Unnamed Item
• Disjoint paths in a rectilinear grid
• Multicommodity flows in planar graphs
• Some simplified NP-complete graph problems
• NP-completeness of some edge-disjoint paths problems
• Hard tiling problems with simple tiles

This page was built for publication: Eulerian disjoint paths problem in grid graphs is NP-complete