PTAS for minimum k-path vertex cover in ball graph
Information Processing Letters，2017，119（）：9-13 | 2017年03月01日 | doi.org/10.1016/j.ipl.2016.11.003
A vertex set F is a k-path vertex cover () 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 , 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 , where and are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum problem in a ball graph whose heterogeneity is bounded by a constant.