 CARMA COLLOQUIUM
 Speaker: Dr Thomas Kalinowski, CARMA, The University of Newcastle
 Title: Incremental network design for minimum spanning trees
 Location: Room V129, Mathematics Building (Callaghan Campus) The University of Newcastle
 Time and Date: 4:00 pm, Thu, 29^{th} Aug 2013
 Abstract:
(Joint work with Konrad Engel and Martin Savelsbergh)
In an incremental network design problem we want to expand an existing network over several time periods, and we are interested in some quality measure for all the intermediate stages of the expansion process. In this talk, we look at the following simple variant: In each time period, we are allowed to add a single edge, the cost of a network is the weight of a minimum spanning tree, and the objective is to minimize the sum of the costs over all time periods. We describe a greedy algorithm for this problem and sketch a proof of the fact that it provides an optimal solution. We also indicate that incremental versions of other basic network optimization problems (shortest path and maximum flow) are NPhard.
 [Permanent link]
