The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs

MaRDI QIDQ3567489zbMATH OpenFDO

Authors Hajime Nagashima, C. S. James Wong

Publication date 17 June 2010

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)

Recommendations

• NP-completeness of some edge-disjoint paths problems
• On the complexity of the disjoint paths problem
• On the complexity of the planar directed edge-disjoint paths problem
• Eulerian disjoint paths problem in grid graphs is NP-complete
• On the complexity of the planar edge-disjoint paths problem with terminals on the outer boundary

This page was built for publication: The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs

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