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

Disjoint pathsGridsNP-completeness

Mathematics Subject Classification ID

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

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

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

Cited in

(16)

• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• NP-completeness of some edge-disjoint paths problems
• Finding edge-disjoint paths in networks: an ant colony optimization algorithm
• Precoloring extension on unit interval graphs
• Multiflow Feasibility: An Annotated Tableau
• scientific article; zbMATH DE number 4202293 (Why is no real title available?)
• Hamiltonian cycles in linear-convex supergrid 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
• The Hamiltonian properties of supergrid graphs
• Solving the edge‐disjoint paths problem using a two‐stage method
• NP-completeness of the Eulerian walk problem for a multiple graph
• The parameterized complexity landscape of the unsplittable flow problem
• The shortest multipaths problem in a capacitated dense channel
• Maximum integer multiflow and minimum multicut problems in two-sided uniform grid graphs
• Disjoint paths in sparse graphs

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)