Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq E_1\subseteq\cdots\subseteq E_r=E$ with $\lvert E_i\setminus E_{i-1}\rvert=1$ which minimizes the sum $\sum_{i=0}^rw(X_i)$ where $w(X_i)$ is the weight of a minimum spanning tree $X_i$ for the subgraph $(V,E_i)$.

The following greedy algorithm yields an optimal solution for this problem: Start with a minimum spanning tree $X_0$ for the subgraph $(V,E_0)$, and then for $i=1,2,\ldots$ find a pair $(e,e')\in X_{i-1}\times(E\setminus X_{i-1})$ of edges such that $(X_{i-1}\setminus\{e\})\cup\{e'\}$ is a spanning tree and $w(e)-w(e')$ is maximal, let $E_i=E_{i-1}\cup\{e'\}$ and $X_i=(X_{i-1}\setminus\{e\}) \cup \{e'\}$ until $X_i$ is a minimum spanning tree for G (and then continue arbitrarily).

This also works for matroids in general.

My question is if this is known and where I can find a reference.

Edit: After not finding any reference for exactly this problem, we've decided to write it up: arxiv


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.