- 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, 29th Aug 2013
(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 NP-hard.
- [Permanent link]