Cardinality constrained path covering problems in grid graphs

DOI10.1002/NET.20022MaRDI QIDQ3156826zbMATH OpenOpenAlexFDO

Authors Nicola Apollonio, Louis Caccetta, Bruno Simeone

Publication date 12 January 2005

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.20022

zbMATH Keywords

algorithmscomplexityGraphsgridspath covering

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Covering paths and trees for planar grids
• On the computational complexity of path cover problems
• On the isometric path partition problem
• Hamiltonian paths in some classes of grid graphs
• Hamiltonian paths in L-shaped grid graphs

Cited in

(6)

• Improved approximation of maximum vertex cover
• scientific article; zbMATH DE number 1517139 (Why is no real title available?)
• Algorithms for solving problems on graphs of bounded pathwidth
• Covering paths and trees for planar grids
• The geodesic cover problem for butterfly networks
• On the computational complexity of path cover problems

This page was built for publication: Cardinality constrained path covering problems in grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3156826)