Title of article :
Eulerian disjoint paths problem in grid graphs is NP-complete
Author/Authors :
D?niel Marx، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2004
Abstract :
We show that the edge disjoint paths problem is NP-complete in directed or undirected rectangular grids, even if the union G+H of the supply and the demand graphs is Eulerian.
Keywords :
NP-completeness , Disjoint paths , Grids
Journal title :
Discrete Applied Mathematics
Journal title :
Discrete Applied Mathematics
