Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
1  
Relevant is David Eppstein's work on dynamic algorithms for minimum spanning trees dx.doi.org/10.1006/jagm.1994.1033 or the preprint at ics.uci.edu/~eppstein/pubs/Epp-TR-92-04.pdf –  András Salamon May 4 '13 at 15:24
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.