Incremental Network Design with Minimum Spanning Trees

Abstract

Given an edge-weighted graph $G=(V,E)$ and a set $E_0\subset E$, the incremental network design problem with minimum spanning trees asks for a sequence of edges $e_1^{\prime },\dots ,e_T^{\prime }\in E\setminus E_0$ minimizing ${\sum }_{t=1}^{T}w(X_t)$ where $w(X_t)$ is the weight of a minimum spanning tree $X_t$ for the subgraph $(V,E_0\cup \{e_1^{\prime },\dots ,e_t^{\prime }\})$ and $T=|E\setminus E_0|$. We prove that this problem can be solved by a greedy algorithm.

9 pages, minor revision based on reviewer comments

Cited by in corpus (1)

• Multi-period Stochastic Network Design for Combined Natural Gas and Hydrogen Distribution