Augmenting graphs to minimize the diameter

Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

4 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
Title of host publicationAlgorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
EditorsLeizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
Pages383-393
Number of pages11
Volume8283 LNCS
DOIs
Publication statusPublished - 2013
Event24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China
Duration: 16 Dec 201318 Dec 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8283 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other24th International Symposium on Algorithms and Computation, ISAAC 2013
CountryChina
CityHong Kong
Period16/12/1318/12/13

Fingerprint Dive into the research topics of 'Augmenting graphs to minimize the diameter'. Together they form a unique fingerprint.

Cite this