Premium
Cardinality constrained path covering problems in grid graphs
Author(s) -
Apollonio N.,
Caccetta L.,
Simeone B.
Publication year - 2004
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20022
Subject(s) - grid , path (computing) , cardinality (data modeling) , time complexity , longest path problem , computer science , row , combinatorics , mathematics , graph , discrete mathematics , mathematical optimization , shortest path problem , geometry , database , data mining , programming language
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