Name
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 |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/net.v44:2 | Networks |
Keywords | Field | DocType |
algorithms,graphs,complexity | Row,Graph,Discrete mathematics,Mathematical optimization,Combinatorics,Cardinal number,Cardinality,Time complexity,Mathematics,Grid,Covering problems,Polynomial method | Journal |
Volume | Issue | ISSN |
44 | 2 | 0028-3045 |
Citations | PageRank | References |
2 | 0.42 | 4 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicola Apollonio | 1 | 39 | 6.58 |
| Lou Caccetta | 2 | 19 | 3.38 |
| Bruno Simeone | 3 | 496 | 54.36 |