2019/04/28 by Liwei Zeng, Zeng, Liwei, Karen Smilowitz +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1904.12258
openalex publication_date 2019/04/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the covering path problem on a grid of R2. We generalize earlier results on a rectangular grid and prove that the covering path cost can be bounded by the area and perimeter of the grid. We provide (2+ε) and (1+ε)-approximations for the problem on a general grid and on a convex grid, respectively.