MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Relevant is David Eppstein's work on dynamic algorithms for minimum spanning trees or the preprint at – András Salamon May 4 '13 at 15:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.