The complexity of the edge disjoint multiple paths problem when constructed over uniformly directed mesh graphs
From MaRDI portal
Publication:3567489
zbMATH Open1200.05232MaRDI QIDQ3567489FDOQ3567489
Authors: Hajime Nagashima, C. S. James Wong 
Publication date: 17 June 2010
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
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)
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)
