\section{The Problem}
The problem of finding a minimum spanning tree of a weighted graph is one of the
-best studied problems in the area of combinatorial optimization and it can be said
-that it stood at the cradle of this discipline. Its colorful history (see \cite{graham:msthistory}
-and \cite{nesetril:history} for the full account) begins in~1926 with
-the pioneering work of Bor\accent23uvka
+best studied problems in the area of combinatorial optimization since its birth.
+Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
+begins in~1926 with the pioneering work of Bor\o{u}vka
\cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
who studied primarily an Euclidean version of the problem related to planning
of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
-algorithm for the general version of the problem. As it was well before the birth of graph
-theory, the language of his paper was complicated, so we will rather state the problem
+algorithm for the general version of the problem. As it was well before the dawn of graph
+theory, the language of his paper was complicated, so we will better state the problem
in contemporary terminology:
\proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
-find its minimum spanning tree, where:
+find its minimum spanning tree, defined as follows:
-\defn For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
+\defn\thmid{mstdef}%
+For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
-\:A~tree $T$ is a \df{spanning tree} of~$G$ if and only if $V(T)=V(G)$ and $E(T)\subseteq E(G)$.
+\:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
+\:A~\df{spanning tree} of $G$ is any its spanning subgraph which is a tree.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
-\:A~spanning tree~$T$ is \df{minimal} iff $w(T)$ is the smallest possible of all spanning trees.
+ When comparing two weights, we will use the terms \df{lighter} and \df{heavier} in the
+ obvious sense.
+\:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
+ is the smallest possible of all the spanning trees of~$G$.
+\:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
+ a union of (minimum) spanning trees of its connected components.
\endlist
-Bor\accent23uvka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
-mostly geometric setting, giving another polynomial algorithm. However, when
+Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
+mostly geometric setting, giving another efficient algorithm. However, when
computer science and graph theory started forming in the 1950's and the
spanning tree problem was one of the central topics of the flourishing new
-disciplines, the previous work was not well known and the algorithms have been
+disciplines, the previous work was not well known and the algorithms had to be
rediscovered several times.
Recently, several significantly faster algorithms were discovered, most notably the
several important theorems to base the algorithms upon. We will follow the theory
developed by Tarjan in~\cite{tarjan:dsna}.
-For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all other
-graphs will be subgraphs of~$G$ containing all of its vertices. We will use the
-same notation for the subgraph and for the corresponding set of edges.
+For the whole section, we will fix a graph~$G$ with edge weights~$w$ and all
+other graphs will be spanning subgraphs of~$G$. We will use the same notation
+for the subgraphs as for the corresponding sets of edges.
First of all, let us show that the weights on edges are not necessary for the
definition of the MST. We can formulate an equivalent characterization using
\:For vertices $x$ and $y$, let $T[x,y]$ denote the (unique) path in~$T$ joining $x$ and~$y$.
\:For an edge $e=xy$ we will call $T[e]:=T[x,y]$ the \df{path covered by~$e$} and
the edges of this path \df{edges covered by~$e$}.
-\:An edge~$e$ is called \df{$T$-light} if it covers a heavier edge, i.e., if there
+\:An edge~$e$ is called \df{light with respect to~$T$} (or just \df{$T$-light}) if it covers a heavier edge, i.e., if there
is an edge $f\in T[e]$ such that $w(f) > w(e)$.
\:An edge~$e$ is called \df{$T$-heavy} if it is not $T$-light.
\endlist
Please note that the above properties also apply to tree edges
which by definition cover only themselves and therefore they are always heavy.
-\lemma\thmid{lightlemma}%
+\lemman{Light edges}\thmid{lightlemma}%
Let $T$ be a spanning tree. If there exists a $T$-light edge, then~$T$
-is not minimal.
+is not minimum.
\proof
-If there is a $T$-light edge~$e$, then there exists an edge $f\in T[e]$ such
-that $w(f)>w(e)$. Now $T-f$ is a forest of two trees with endpoints of~$e$
+If there is a $T$-light edge~$e$, then there exists an edge $e'\in T[e]$ such
+that $w(e')>w(e)$. Now $T-e'$ is a forest of two trees with endpoints of~$e$
located in different components, so adding $e$ to this forest must restore
-connectivity and $T':=T-f+e$ is another spanning tree with weight $w(T')
-= w(T)-w(f)+w(e) < w(T)$. Hence $T$ could not have been minimal.
+connectivity and $T':=T-e'+e$ is another spanning tree with weight $w(T')
+= w(T)-w(e')+w(e) < w(T)$. Hence $T$ could not have been minimum.
\qed
\figure{mst2.eps}{278pt}{An edge exchange as in the proof of Lemma~\thmref{lightlemma}}
$T_{i+1}=T_i - e_i + e_i^\prime$ where $e_i\in T_i$ and $e_i^\prime\in T'$.
\proof
-By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$, then
-both trees are identical and an empty sequence suffices. Otherwise, the trees are different,
-but they are of the same size, so there must exist an edge $e'\in T'\setminus T$.
+By induction on $d(T,T'):=\vert T\symdiff T'\vert$. When $d(T,T')=0$,
+both trees are identical and no exchanges are needed. Otherwise, the trees are different,
+but as they are of the same size, there must exist an edge $e'\in T'\setminus T$.
The cycle $T[e']+e'$ cannot be wholly contained in~$T'$, so there also must
exist an edge $e\in T[e']\setminus T'$. Exchanging $e$ for~$e'$ yields a spanning
tree $T^*:=T-e+e'$ such that $d(T^*,T')=d(T,T')-2$ and we can apply the induction
\figure{mst1.eps}{295pt}{One step of the proof of Lemma~\thmref{xchglemma}}
\lemman{Monotone exchanges}\thmid{monoxchg}%
-Let $T$ be a spanning tree such that there are no $T$-light edges and $T$
+Let $T$ be a spanning tree such that there are no $T$-light edges and $T'$
be an arbitrary spanning tree. Then there exists a sequence of edge exchanges
transforming $T$ to~$T'$ such that the weight does not increase in any step.
We improve the argument from the previous proof, refining the induction step.
When we exchange $e\in T$ for $e'\in T'\setminus T$ such that $e\in T[e']$,
the weight never drops, since $e'$ is not a $T$-light edge and therefore
-$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\le w(T)$.
+$w(e') \ge w(e)$, so $w(T^*)=w(T)-w(e)+w(e')\ge w(T)$.
-To allow the induction to proceed, we have to make sure that there are still
-no light edges with respect to~$T^*$. In fact, it is enough to avoid $T^*$-light
-edges in $T'\setminus T^*$, since these are the only edges considered by the
-induction step. Instead of picking $e'$ arbitrarily, we will pick the lightest
-edge available. Now consider an edge $f\in T'\setminus T^*$. We want to show
-that $f$ is heavier than all edges on $T^*[f]$.
+To keep the induction going, we have to make sure that there are still no light
+edges with respect to~$T^*$. In fact, it is enough to avoid such edges in
+$T'\setminus T^*$, since these are the only edges considered by the induction
+steps. To accomplish that, we replace the so far arbitrary choice of $e'\in T'\setminus T$
+by picking the lightest such edge.
-The path $T^*[f]$ is either the original path $T[f]$ (if $e\not\in T[f]$)
-or $T[f] \symdiff C$, where $C$ is the cycle $T[e']+e$. The first case is
-trivial, in the second case $w(f)\ge w(e')$ and all other edges on~$C$
-are lighter than~$e'$.
+Now consider an edge $f\in T'\setminus T^*$. We want to show that $f$ is not
+$T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
+either equal to the original path $T[f]$ (if $e\not\in T[f]$) or to $T[f] \symdiff C$,
+where $C$ is the cycle $T[e']+e'$. The former case is trivial, in the latter one
+$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
+than~$e'$ as $e'$ was not $T$-light.
\qed
-\theorem
-A~spanning tree~$T$ is minimal iff there is no $T$-light edge.
+\thm\thmid{mstthm}%
+A~spanning tree~$T$ is minimum iff there is no $T$-light edge.
\proof
-If~$T$ is minimal, then by Lemma~\thmref{lightlemma} there are no $T$-light
+If~$T$ is minimum, then by Lemma~\thmref{lightlemma} there are no $T$-light
edges.
Conversely, when $T$ is a spanning tree without $T$-light edges
-and $T_{min}$ is an arbitrary minimal spanning tree, then according to the Monotone
-exchange lemma~\thmref{monoxchg} there exists a non-decreasing sequence
+and $T_{min}$ is an arbitrary minimum spanning tree, then according to the Monotone
+exchange lemma (\thmref{monoxchg}) there exists a non-decreasing sequence
of exchanges transforming $T$ to $T_{min}$, so $w(T)\le w(T_{min})$
-and thus $T$~is also minimal.
+and thus $T$~is also minimum.
\qed
+In general, a single graph can have many minimum spanning trees (for example
+a complete graph on~$n$ vertices and unit edge weights has $n^{n-2}$
+minimum spanning trees according to the Cayley's formula \cite{cayley:trees}).
+However, as the following theorem shows, this is possible only if the weight
+function is not injective.
+
+\thmn{MST uniqueness}
+If all edge weights are distinct, then the minimum spanning tree is unique.
+
+\proof
+Consider two minimum spanning trees $T_1$ and~$T_2$. According to the previous
+theorem, there are no light edges with respect to neither of them, so by the
+Monotone exchange lemma (\thmref{monoxchg}) there exists a sequence of non-decreasing
+edge exchanges going from $T_1$ to $T_2$. As all edge weights all distinct,
+these edge exchanges must be in fact strictly increasing. On the other hand,
+we know that $w(T_1)=w(T_2)$, so the exchange sequence must be empty and indeed
+$T_1$ and $T_2$ must be identical.
+\qed
+
+\rem\thmid{edgeoracle}%
+To simplify the description of MST algorithms, we will expect that the weights
+of all edges are distinct and that instead of numeric weights (usually accompanied
+by problems with representation of real numbers in algorithms) we will be given
+a comparison oracle, that is a function which answers questions ``$w(e)<w(f)$?'' in
+constant time. In case the weights are not distinct, we can easily break ties by
+comparing some unique edge identifiers and according to our characterization of
+minimum spanning trees, the unique MST of the new graph will still be a MST of the
+original graph. In the few cases where we need a more concrete input, we will
+explicitly state so.
+
+\section{The Red-Blue Meta-Algorithm}
+
+Most MST algorithms can be described as special cases of the following procedure
+(again following \cite{tarjan:dsna}):
+
+\algn{Red-Blue Meta-Algorithm}
+\algo
+\algin A~graph $G$ with an edge comparison oracle (see \thmref{edgeoracle})
+\:In the beginning, all edges are colored black.
+\:Apply rules as long as possible:
+\::Either pick a cut~$C$ such that its lightest edge is not blue \hfil\break and color this edge blue, \cmt{Blue rule}
+\::Or pick a cycle~$C$ such that its heaviest edge is not red \hfil\break and color this edge \hphantas{red.}{blue.} \cmt{Red rule}
+\algout Minimum spanning tree of~$G$ consisting of edges colored blue.
+\endalgo
+
+\rem
+This procedure is not a proper algorithm, since it does not specify how to choose
+the rule to apply. We will however prove that no matter how the rules are applied,
+the procedure always stops and gives the correct result. Also, it will turn out
+that each of the classical MST algorithms can be described as a specific way
+of choosing the rules in this procedure, which justifies the name meta-algorithm.
+
+\proclaim{Notation}%
+We will denote the unique minimum spanning tree of the input graph by~$T_{min}$.
+We intend to prove that this is also the output of the procedure.
+
+\lemman{Blue lemma}
+When an edge is colored blue in any step of the procedure, it is contained in the minimum spanning tree.
+
+\proof
+By contradiction. Let $e$ be an edge painted blue as the lightest edge of a cut~$C$.
+If $e\not\in T_{min}$, then there must exist an edge $e'\in T_{min}$ which is
+contained in~$C$ (take any pair of vertices separated by~$C$, the path
+in~$T_{min}$ joining these vertices must cross~$C$ at least once). Exchanging
+$e$ for $e'$ in $T_{min}$ yields an even lighter spanning tree since
+$w(e)<w(e')$. \qed
+
+\lemman{Red lemma}
+When an edge is colored red in any step of the procedure, it is not contained in the minimum spanning tree.
+
+\proof
+Again by contradiction. Assume that $e$ is an edge painted red as the heaviest edge
+of a cycle~$C$ and that $e\in T_{min}$. Removing $e$ causes $T_{min}$ to split to two
+components, let us call them $T_x$ and $T_y$. Some vertices of~$C$ now lie in $T_x$,
+the others in $T_y$, so there must exist in edge $e'\ne e$ such that its endpoints
+lie in different components. Since $w(e')<w(e)$, exchanging $e$ for~$e'$ yields
+a lighter spanning tree than $T_{min}$.
+\qed
+
+\figure{mst-rb.eps}{289pt}{Proof of the Blue (left) and Red (right) lemma}
+
+\lemman{Black lemma}
+As long as there exists a black edge, at least one rule can be applied.
+
+\proof
+Assume that $e=xy$ be a black edge. Let us denote $M$ the set of vertices
+reachable from~$x$ using only blue edges. If $y$~lies in~$M$, then $e$ together
+with some blue path between $x$ and $y$ forms a cycle and it must be the heaviest
+edge on this cycle. This holds because all blue edges have been already proven
+to be in $T_{min}$ and there can be no $T_{min}$-light edges (see Theorem~\thmref{mstthm}).
+In this case we can apply the red rule.
+
+On the other hand, if $y\not\in M$, then the cut formed by all edges between $M$
+and $V(G)\setminus M$ contains no blue edges, therefore we can use the blue rule.
+\qed
+
+\figure{mst-bez.eps}{295pt}{Configurations in the proof of the Black lemma}
+
+\thmn{Red-Blue correctness}
+For any selection of rules, the Red-Blue procedure stops and the blue edges form
+the minimum spanning tree of the input graph.
+
+\proof
+To prove that the procedure stops, let us notice that no edge is ever recolored,
+so we must run out of black edges after at most~$m$ steps. Recoloring
+to the same color is avoided by the conditions built in the rules, recoloring to
+a different color would mean that the an edge would be both inside and outside~$T_{min}$
+due to our Red and Blue lemmata.
+
+When no further rules can be applied, the Black lemma guarantees that all edges
+are colored, so by the Blue lemma all blue edges are in~$T_{min}$ and by the Red
+lemma all other (red) edges are outside~$T_{min}$, so the blue edges are exactly~$T_{min}$.
+\qed
+
+\section{Classical algorithms}
+
+The three classical MST algorithms can be easily stated in terms of the Red-Blue meta-algorithm.
+For each of them, we first state the general version of the algorithm, then we prove that
+it gives the correct result and finally we discuss the time complexity of various
+implementations.
+
+\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst} and others}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\:$T\=$ a forest consisting of vertices of~$G$ and no edges.
+\:While $T$ is not connected:
+\::For each component $T_i$ of~$T$, choose the lightest edge $e_i$ from the cut
+ separating $T_i$ from the rest of~$T$.
+\::Add all $e_i$'s to~$T$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma
+Bor\o{u}vka's algorithm returns the MST of the input graph.
+
+\proof
+In every iteration of the algorithm, $T$ is a blue subgraph,
+because every addition of some edge~$e_i$ to~$T$ is a straightforward
+application of the Blue rule. We stop when the blue subgraph is connected, so
+we do not need the Red rule to explicitly exclude edges.
+
+It remains to show that adding the edges simultaneously does not
+produce a cycle. Consider the first iteration of the algorithm where $T$ contains some cycle~$C$. Without
+loss of generality we can assume that $C=T_1[u_1v_1]\,v_1u_2\,T_2[u_2v_2]\,v_2u_3\,T_3[u_3v_3]\, \ldots \,T_k[u_kv_k]\,v_ku_1$.
+Each component $T_i$ has chosen its lightest incident edge~$e_i$ as either the edge $v_iu_{i+1}$
+or $v_{i-1}u_i$ (indexing cyclically). Assume that $e_1=v_1u_2$ (otherwise we reverse the orientation
+of the cycle). Then $e_2=v_2u_3$ and $w(e_2)<w(e_1)$ and so on, giving $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$,
+which is a contradiction. (Note that distinctness of edge weights was crucial here.)
+\qed
+
+\lemma
+In each iteration of the algorithm, the number of trees in~$T$ drops at least twice.
+
+\proof
+Each tree gets merged with at least one neighboring trees, so each of the new trees
+consists of at least two original trees.
+\qed
+
+\cor
+The algorithm stops in $\O(\log n)$ iterations.
+
+\lemma
+Each iteration can be carried out in time $\O(m)$.
+
+\proof
+Following \cite{mm:mst},
+we assign a label to each tree and we keep a mapping from vertices to the
+labels of the trees they belong to. We scan all edges, map their endpoints
+to the particular trees and for each tree we maintain the lightest incident edge
+so far encountered. Instead of merging the trees one by one (which would be too
+slow), we build an auxilliary graph whose vertices are labels of the original
+trees and edges correspond to the chosen lightest inter-tree edges. We find connected
+components of this graph, these determine how the original labels are translated
+to the new labels.
+\qed
+
+\thm
+Bor\o{u}vka's algorithm finds the MST in time $\O(m\log n)$.
+
+\proof
+Follows from the previous lemmata.
+\qed
+
+\algn{Jarn\'\i{}k \cite{jarnik:ojistem}, Prim \cite{prim:mst}, Dijkstra \cite{dijkstra:mst}}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\:$T\=$ a single-vertex tree containing any vertex of~$G$.
+\:While there are vertices outside $T$:
+\::Pick the lightest edge $uv$ such that $u\in V(T)$ and $v\not\in V(T)$.
+\::$T\=T+uv$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma
+Jarn\'\i{}k's algorithm returns the MST of the input graph.
+
+\proof
+During the course of the algorithm, $T$ is always a blue tree. Step~4 corresponds to applying
+the Blue rule to a cut between~$T$ and the rest of the given graph. We need not care about
+the remaining edges, since for a connected graph the algorithm always stops with the right
+number of blue edges.
+\qed
+
+\impl
+The most important part of the algorithm is finding \em{neighboring edges,} i.e., edges
+going between $T$ and $V(G)\setminus T$. In the straightforward implementation,
+searching for the lightest neighboring edge takes $\Theta(m)$ time, so the whole
+algorithm runs in time $\Theta(mn)$.
+
+We can do much better by using a binary
+heap to hold all neighboring edges. In each iteration, we find and delete the
+minimum edge from the heap and once we expand the tree, we insert the newly discovered
+neighboring edges to the heap while deleting the neighboring edges which become
+internal to the new tree. Since there are always at most~$m$ edges in the heap,
+each heap operation takes $\O(\log m)=\O(\log n)$ time. For every edge, we perform
+at most one insertion and at most one deletion, so we spend $\O(m\log n)$ time in total.
+From this, we can conclude:
+
+\thm
+Jarn\'\i{}k's algorithm finds the MST of the graph in time $\O(m\log n)$.
+
+\rem
+We will show several faster implementations in section \secref{fibonacci}.
+
+\algn{Kruskal \cite{kruskal:mst}, the Greedy algorithm}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\:Sort edges of~$G$ by their increasing weight.
+\:$T\=\emptyset$. \cmt{an empty spanning subgraph}
+\:For all edges $e$ in their sorted order:
+\::If $T+e$ is acyclic, add~$e$ to~$T$.
+\::Otherwise drop~$e$.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\lemma
+Kruskal's algorithm returns the MST of the input graph.
+
+\proof
+In every step, $T$ is a forest of blue trees. Adding~$e$ to~$T$
+in step~4 applies the Blue rule on the cut separating two components of~$T$ ($e$ is the lightest,
+because all other edges of the cut have not been considered yet). Dropping~$e$ in step~5 corresponds
+to the red rule on the cycle found ($e$~must be the heaviest, since all other edges of the
+cycle have been already processed). At the end of the algorithm, all edges have been colored,
+so~$T$ must be the~MST.
+\qed
+
+\impl
+Except for the initial sorting, which in general takes $\Theta(m\log n)$ time, the only
+other non-trivial operation is detection of cycles. What we need is a data structure
+for maintaining connected components, which supports queries and edge insertion.
+The following theorem shows that it can be done with a surprising efficiency.
+
+\thmn{Incremental connectivity}
+When only edge insertions and queries are allowed, connected components
+can be maintained in $\O(\alpha(n))$ time amortized per operation.
+
+\proof
+Proven by Tarjan and van Leeuwen in \cite{tarjan:setunion}.
+\qed
+
+\FIXME{Define Ackermann's function. Use $\alpha(m,n)$?}
+
+\rem
+The cost of the operations on components is of course dwarfed by the complexity
+of sorting, so a much simpler (at least in terms of its analysis) data
+structure would be sufficient, as long as it has $\O(\log n)$ amortized complexity
+per operation. For example, we can label vertices with identifiers of the
+corresponding components and always recolor the smaller of the two components.
+
+\thm
+Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$
+or $\O(m\alpha(n))$ if the edges are already sorted by their weights.
+
+\proof
+Follows from the above analysis.
+\qed
+
+\section{Contractive algorithms}
+
+While the classical algorithms are based on growing suitable trees, they
+can be also reformulated in terms of edge contraction. Instead of keeping
+a forest of trees, we can keep each tree contracted to a single vertex.
+This replaces the relatively complex tree-edge incidencies by simple
+vertex-edge incidencies, potentially speeding up the calculation at the
+expense of having to perform the contractions.
+
+We will show a contractive version of the Bor\o{u}vka's algorithm
+in which these costs are carefully balanced, leading for example to
+a linear-time algorithm for MST in planar graphs.
+
+There are two definitions of edge contraction which differ when an edge of a
+triangle is contracted. Either we unify the other two edges to a single edge
+or we keep them as two parallel edges, leaving us with a multigraph. We will
+use the multigraph version and show that we can easily reduce the multigraph
+to a simple graph later. (See \thmref{contract} for the exact definitions.)
+
+We only need to be able to map edges of the contracted graph to the original
+edges, so each edge will carry a unique label $l(e)$ which will be preserved by
+contractions.
+
+\lemman{Flattening a multigraph}%
+Let $G$ be a multigraph and $G'$ its subgraph such that all loops have been
+removed and each bundle of parallel edges replaced by its lightest edge.
+Then $G'$~has the same MST as~$G$.
+
+\proof
+Loops can be never used in a spanning tree. If there is a spanning tree~$T$
+containing a removed edge~$e$ parallel to an edge~$e'\in G'$, exchaning $e'$
+for~$e$ in~$T$ makes it lighter. \qed
+
+\rem Removal of the heavier of a pair of parallel edges can be also viewed
+as an application of the Red rule on a two-edge cycle. And indeed it is, the
+Red-Blue procedure works on multigraphs as well as on simple graphs and all the
+classical algorithms also do. We only have to be more careful in the
+formulations and proofs, which we preferred to avoid. We also note that most of
+the algorithms can be run on disconnected graphs with little or no
+modifications.
+
+\algn{Contracting version of Bor\o{u}vka's algorithm}
+\algo
+\algin A~graph~$G$ with an edge comparison oracle.
+\:$T\=\emptyset$.
+\:$l(e)\=e$ for all edges~$e$. \cmt{Initialize the labels.}
+\:While $n(G)>1$:
+\::For each vertex $v_i$ of~$G$, let $e_i$ be the lightest edge incident to~$v_i$.
+\::$T\=T\cup \{ l(e_i) \}$. \cmt{Remember labels of all selected edges.}
+\::Contract $G$ along all edges $e_i$, inheriting labels and weights.
+\::Flatten $G$, removing parallel edges and loops.
+\algout Minimum spanning tree~$T$.
+\endalgo
+
+\FIXME{Show how to do contractions in linear time}
+
+\FIXME{Analyse performance on planar graphs}
+
+\section{Minor-closed graph classes}
+
+\section{Using Fibonacci heaps}
+\secid{fibonacci}
+
+% G has to be connected, so m=O(n)
% mention Steiner trees
% mention matroids
% sorted weights
+% \O(...) as a set?
\endpart
projects / saga.git / blobdiff