Cardinality constrained path covering problems in grid graphs
Nicola Apollonio, L. Caccetta, Bruno Simeone · Networks · 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 results. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(2), 120–131 2004