文章基本信息

标题：Augmenting Graphs to Minimize the Radius
本地全文：下载
作者：Gudmundsson, Joachim ; Sha, Yuan ; Yao, Fan 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：212
DOI：10.4230/LIPIcs.ISAAC.2021.45
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the problem of augmenting a metric graph by adding k edges while minimizing the radius of the augmented graph. We give a simple 3-approximation algorithm and show that there is no polynomial-time (5/3-ε)-approximation algorithm, for any ε > 0, unless P = NP. We also give two exact algorithms for the special case when the input graph is a tree, one of which is generalized to handle metric graphs with bounded treewidth.
关键词：graph augmentation;radius;approximation algorithm