from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
and Pettie \cite{pettie:ackermann}, to an~algorithm by Pettie \cite{pettie:optimal}
-whose time complexity is provably optimal.
+whose time complexity is provably optimal. Frequently, the most important ingredients
+were advances in data structures used to represent the graph.
In the upcoming chapters, we will explore this colorful universe of MST algorithms.
We will meet the canonical works of the classics, the clever ideas of their successors,
$T^*$-light, i.e., that it is heavier than all edges on $T^*[f]$. The path $T^*[f]$ is
either identical 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 we have
-$w(f)\ge w(e')$ due to the choice of $e'$ and all other edges on~$C$ are lighter
+$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
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.
+\looseness=1 %%HACK%%
\qed
\nota\id{mstnota}%
\nota\id{deltanota}%
We will use $\delta(M)$ to denote the cut separating~$M$ from its complement.
-That is, $\delta(M) = E \cap (M \times (V\setminus M))$. We will also abbreviate
-$\delta(\{v\})$ as~$\delta(v)$.
+That is, $\delta(M) = \{ uv \in E \mid u\in M, v\not\in M \}$.
+We will also abbreviate $\delta(\{v\})$ as~$\delta(v)$.
\thmn{Red-Blue correctness}%
For any selection of rules, the Red-Blue procedure stops and the blue edges form
the \df{neighboring edges} of the tree). We add all such edges to the forest and
proceed with the next iteration.
-\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Sollin \cite{sollin:mst}, and others}
+\algn{Bor\o{u}vka \cite{boruvka:ojistem}, Choquet \cite{choquet:mst}, Florek et al.~\cite{florek:liaison}, Sollin \cite{sollin:mst}}
\algo
\algin A~graph~$G$ with an edge comparison oracle.
\:$T\=$ a forest consisting of vertices of~$G$ and no edges.
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 a~cycle~$C$. Without
+produce a~cycle. Consider the first iteration of the algorithm where $T$ contains a~cycle~$C$. Without
loss of generality we can assume that:
$$C=T_1[u_1,v_1]\,v_1u_2\,T_2[u_2,v_2]\,v_2u_3\,T_3[u_3,v_3]\, \ldots \,T_k[u_k,v_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). Suppose 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 we can continue in the same way,
-getting $w(e_1)>w(e_2)>\ldots>w(e_k)>w(e_1)$, which is a contradiction.
+getting $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
The Jarn\'\i{}k's algorithm computes the MST of a~given graph in time $\O(m\log n)$.
\rem
-We will show several faster implementations in section \ref{iteralg}.
+We will show several faster implementations in Section \ref{iteralg}.
\paran{Kruskal's algorithm}%
The last of the three classical algorithms processes the edges of the
the same component. If they do not, addition of this edge connects both components into one,
so we perform $\<Union>(u,v)$ to merge the equivalence classes.
-Tarjan has shown that there is a~data structure for the DSU problem
+Tarjan \cite{tarjan:setunion} has shown that there is a~data structure for the DSU problem
of surprising efficiency:
\thmn{Disjoint Set Union, Tarjan \cite{tarjan:setunion}}\id{dfu}%
comprising of $n$~\<Union>s intermixed with $m\ge n$~\<Find>s can be processed in time
$\O(m\timesalpha(m,n))$, where $\alpha(m,n)$ is a~certain inverse of the Ackermann's function
(see Definition \ref{ackerinv}).
-
-\proof
-See \cite{tarjan:setunion}.
\qed
-This completes the following theorem:
+Using this data structure, we get the following bound:
\thm\id{kruskal}%
The Kruskal's algorithm finds the MST of a given graph in time $\O(m\log n)$.
On planar graphs, the algorithm runs much faster:
-\thmn{Contractive Bor\o{u}vka on planar graphs}\id{planarbor}%
+\thmn{Contractive Bor\o{u}vka's algorithm on planar graphs, Cheriton and Tarjan \cite{cheriton:mst}}\id{planarbor}%
When the input graph is planar, the Contractive Bor\o{u}vka's algorithm runs in
time $\O(n)$.
\lemman{Contraction of MST edges}\id{contlemma}%
Let $G$ be a weighted graph, $e$~an arbitrary edge of~$\mst(G)$, $G/e$ the multigraph
produced by contracting~$e$ in~$G$, and $\pi$ the bijection between edges of~$G-e$ and
-their counterparts in~$G/e$. Then: $$\mst(G) = \pi^{-1}[\mst(G/e)] + e.$$
+their counterparts in~$G/e$. Then $\mst(G) = \pi^{-1}[\mst(G/e)] + e.$
\proof
% We seem not to need this lemma for multigraphs...
\figure{hedgehog.eps}{\epsfxsize}{A~hedgehog $H_{5,2}$ (quills bent to fit in the picture)}
\lemma
-A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a graph isomorphic with $H_{a,k-1}$.
+A~single iteration of the contractive algorithm reduces~$H_{a,k}$ to a~graph isomorphic with $H_{a,k-1}$.
\proof
Each vertex is incident with an edge of some distractor, so the algorithm does not select
projects / saga.git / blobdiff