Eulerian disjoint paths problem in grid graphs is NP-complete
Author:
- Dániel MarxDMDániel Marx
- 1 September 2004
- journal article
- research article
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 143 (1-3) , 336-341
Abstract
No abstract availableKeywords
This publication has 5 references indexed in Scilit:
- Hard Tiling Problems with Simple TilesDiscrete & Computational Geometry, 2001
- NP-completeness of some edge-disjoint paths problemsDiscrete Applied Mathematics, 1995
- Disjoint paths in a rectilinear gridCombinatorica, 1982
- Multicommodity flows in planar graphsJournal of Combinatorial Theory, Series B, 1981
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976