Thursday 30 April 2015 from 12:00–13:00 in Carslaw 535A
Augmenting Graphs to Minimize the Diameter
Joachim Gudmundsson (School of IT, Sydney)
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 a Fixed Parameter Tractable PT 4-approximation algorithm for the problem.
Joint work with Fabrizio Frati, Serge Gaspers and Luke Mathieson.