Augmenting Graphs to Minimize the Diameter

Publication Type:
Journal Article
Algorithmica, 2015, 72 (4), pp. 995 - 1010
Issue Date:
Filename Description Size
10.1007_978-3-642-45030-3_36.pdfPublished Version308.89 kB
Adobe PDF
Full metadata record
© 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: