Augmenting Graphs to Minimize the Diameter

Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson*, Luke Mathieson

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

Abstract

We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.

Original languageEnglish
Pages (from-to)995-1010
Number of pages16
JournalAlgorithmica
Volume72
Issue number4
DOIs
Publication statusPublished - 19 Aug 2015

Keywords

  • Approximation algorithms
  • Graph Algorithms
  • Parametrized complexity

Fingerprint

Dive into the research topics of 'Augmenting Graphs to Minimize the Diameter'. Together they form a unique fingerprint.

Cite this