DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.45

Augmenting Graphs to Minimize the Radius

Authors: Joachim Gudmundsson, Yuan Sha, and Fan Yao

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

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.

Cite as

Joachim Gudmundsson, Yuan Sha, and Fan Yao. Augmenting Graphs to Minimize the Radius. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 45:1-45:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gudmundsson_et_al:LIPIcs.ISAAC.2021.45,
  author =	{Gudmundsson, Joachim and Sha, Yuan and Yao, Fan},
  title =	{{Augmenting Graphs to Minimize the Radius}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{45:1--45:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.45},
  URN =		{urn:nbn:de:0030-drops-154785},
  doi =		{10.4230/LIPIcs.ISAAC.2021.45},
  annote =	{Keywords: graph augmentation, radius, approximation algorithm}
}

Search Results

Documents authored by Yao, Fan

Augmenting Graphs to Minimize the Radius

Abstract

Cite as

Thanks for your feedback!

Could not send message