SACT Seminar: Reduction of the Radius of a Graph by Adding Edges

Time: 1:00 pm Tuesday, 14th February 2017.

Location: SIT 459

Speaker: Michael Rizzuto, University of Sydney

Title: Reduction of the Radius of a Graph by Adding Edges

Abstract:
Given a graph and a maximum number of extra edges, we wish to find the minimum radius achievable by adding these edges to the graph.
A solution for trees was found through a greedy algorithm, and a solution for general graphs was obtained through the use of a tree decomposition and dynamic programming.