Thursday 30 April 2015 from 12:00–13:00 in Carslaw 535A

Augmenting Graphs to Minimize the Diameter

Joachim Gudmundsson (School of IT, Sydney)


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 a Fixed Parameter Tractable PT 4-approximation algorithm for the problem.

Joint work with Fabrizio Frati, Serge Gaspers and Luke Mathieson.

About this page.               For questions or comments please contact