Augmenting Graphs to Minimize the Diameter

Publication Type:
Journal Article
Citation:
Algorithmica, 2015, 72 (4), pp. 995 - 1010
Issue Date:
2015-08-19
Full metadata record
Files in This Item:
Filename Description Size
1309.5172v1.pdfSubmitted Version191.75 kB
Adobe PDF
© 2014, Springer Science+Business Media New York. 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$$4-approximation algorithm for the problem.
Please use this identifier to cite or link to this item: