Incremental Network Design with Minimum Spanning Trees

Abstract

Given an edge-weighted graph G = (V,E) and a set E₀⊂E , the incremental network design problem with minimum spanning trees asks for a sequence of edges e′ ₁ , … , e ′ _T ∈ E ∖ E ₀ minimizing ∑ ^T _{t = 1} w ( X _t ) where w(X_t) is the weight of a minimum spanning tree X_t for the subgraph (V,E₀∪ { e ′ ₁ , … , e ′ _T } ) and T=|E∖ E 0 |. We prove that this problem can be solved by a greedy algorithm.