您当前所在位置: 首页 > 学者

张昭

  • 20浏览

  • 0点赞

  • 0收藏

  • 0分享

  • 0下载

  • 0评论

  • 引用

期刊论文

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

URL:https://www.sciencedirect.com/science/article/abs/pii/S0020019016301673

摘要/描述

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.

学者未上传该成果的PDF文件,请等待学者更新

我要评论

全部评论 0

本学者其他成果

    同领域成果