Incremental Network Design with Minimum Spanning Trees
Konrad Engel, Thomas Kalinowski, Martin W. P. Savelsbergh · 2013
Given an edge-weighted graph G = (V,E) and a set E0⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ 1 , … , e ′ T ∈ E ∖ E 0 minimizing ∑ T t = 1 w ( X t ) where w(Xt) is the weight of a minimum spanning tree Xt for the subgraph (V,E0∪ { e ′ 1 , … , e ′ T } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.