Eulerian disjoint paths problem in grid graphs is NP-complete

DOI10.1016/J.DAM.2003.12.003MaRDI QIDQ1887070zbMATH OpenOpenAlexFDO

Authors 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• NP-completeness of some edge-disjoint paths problems
• scientific article; zbMATH DE number 1303036
• On the complexity of the planar directed edge-disjoint paths problem
• On the complexity of the disjoint paths problem
• The disjoint shortest paths problem

Cites work

• scientific article; zbMATH DE number 16298 (Why is no real title available?)
• Disjoint paths in a rectilinear grid
• Hard tiling problems with simple tiles
• Multicommodity flows in planar graphs
• NP-completeness of some edge-disjoint paths problems
• Some simplified NP-complete graph problems

Cited in

(13)

• Disjoint paths in sparse graphs
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• Solving the edge‐disjoint paths problem using a two‐stage method
• The shortest multipaths problem in a capacitated dense channel
• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs
• The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs
• Precoloring extension on unit interval graphs
• Hamiltonian cycles in linear-convex supergrid graphs
• The Hamiltonian properties of supergrid graphs
• Multiflow Feasibility: An Annotated Tableau
• NP-completeness of the Eulerian walk problem for a multiple graph
• NP-completeness of some edge-disjoint paths problems

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

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