In this article we continue our study on the complexity of Path Covering Problems started in [2]. Here, taking one further step, we investigate the complexity of the problem on grids. For special classes of grids (general grids, grids with a fixed number of rows, ladders), and several special unweighted path collections (general paths, paths of length 2, L-shaped paths, pipes, hooks, staples) we either give polynomial-time algorithms or prove NP-completeness results
Cardinality constrained path covering problems in grid graphs
Apollonio N;
2004
Abstract
In this article we continue our study on the complexity of Path Covering Problems started in [2]. Here, taking one further step, we investigate the complexity of the problem on grids. For special classes of grids (general grids, grids with a fixed number of rows, ladders), and several special unweighted path collections (general paths, paths of length 2, L-shaped paths, pipes, hooks, staples) we either give polynomial-time algorithms or prove NP-completeness resultsFile in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
