\input macros.tex

\def\rawchapter#1{\vensure{1in}\bigbreak\bigbreak
\leftline{\chapfont #1}
\bigskip
}

\chapter{Introduction}

This thesis tells the story of two well-established problems of algorithmic
graph theory: the minimum spanning trees and ranks of permutations. At distance,
both problems seem to be simple, boring and already solved, because we have poly\-nom\-ial-time
algorithms for them since ages. But when we come closer and seek algorithms that
are really efficient, the problems twirl and twist and withstand many a~brave
attempt at the optimum solution. They also reveal a~vast and diverse landscape
of a~deep and beautiful theory. Still closer, this landscape turns out to be interwoven
with the intricate details of various models of computation and even of arithmetics
itself.

I have tried to cover all known important results on both problems and unite them
in a~single coherent theory. At many places, I have attempted to contribute my own
little stones to this mosaic: several new results, simplifications of existing
ones, and last, but not least filling in important details where the original
authors have missed some.

When compared with the earlier surveys on the minimum spanning trees, most
notably Graham and Hell \cite{graham:msthistory} and Eisner \cite{eisner:tutorial},
this work adds many of the recent advances, the dynamic algorithms and
also the relationship with computational models. No previous work covering
the ranking problems in their entirety is known.

The early parts of this thesis also served as a~basis for a~course on graph
algorithms which I was teaching at our faculty during years 2006 and~2007. They are
included in the textbook \cite{mm:ga} which I have written for this course.

I~have tried to stick to the usual notation except where it was too inconvenient.
Most symbols are defined at the place where they are used for the first time.
To avoid piling up too many symbols at places that speak about a~single fixed graph,
this graph is always called~$G$, its set of vertices and edges are denoted by $V$
and~$E$ respectively, and I~also use~$n$ for the number of its vertices and $m$~for
the number of edges. At places where there could be a~danger of confusion, more explicit notation
is used instead.

\chapter{Minimum Spanning Trees}

\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 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 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, defined as follows:

\defn\id{mstdef}%
For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
\itemize\ibull
\:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
\:A~\df{spanning tree} of~$G$ is any spanning subgraph of~$G$ that is a tree.
\:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
  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 among 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\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
mostly geometric setting. He has discovered 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 had to be
rediscovered several times.

In the next 50 years, several significantly faster algorithms were discovered, ranging
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.

\chapter{Bibliography}

\dumpbib

\vfill\eject
\ifodd\pageno\else\hbox{}\fi

\bye
