SMS scnews item created by Stephan Tillmann at Wed 29 Apr 2015 1419
Type: Seminar
Distribution: World
Expiry: 29 Jul 2015
Calendar1: 30 Apr 2015 1200-1300
CalLoc1: Carslaw 535A
Auth: tillmann@p710.pc (assumed)

Geometry & Topology

Augmenting Graphs to Minimize the Diameter

Joachim Gudmundsson (School of IT, Sydney)

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

Please join us for lunch after the talk!


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.