Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950945 | Information Processing Letters | 2017 | 5 Pages |
Abstract
A vertex set F is a k-path vertex cover (VCPk) of graph G if every path of G on k vertices contains at least one vertex from F. A graph G is a d-dimensional ball graph if each vertex of G corresponds to a ball in Rd, two vertices are adjacent in G if and only if their corresponding balls have nonempty intersection. The heterogeneity of a ball graph is defined to be rmax/rmin, where rmax and rmin are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum VCPk problem in a ball graph whose heterogeneity is bounded by a constant.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Zhao Zhang, Xiaoting Li, Yishuo Shi, Hongmei Nie, Yuqing Zhu,