abstract.tex

   1 \input macros.tex
   2
   3 \def\rawchapter#1{\vensure{1in}\bigbreak\bigbreak
   4 \leftline{\chapfont #1}
   5 \bigskip
   6 }
   7
   8 \chapter{Introduction}
   9
  10 This thesis tells the story of two well-established problems of algorithmic
  11 graph theory: the minimum spanning trees and ranks of permutations. At distance,
  12 both problems seem to be simple, boring and already solved, because we have poly\-nom\-ial-time
  13 algorithms for them since ages. But when we come closer and seek algorithms that
  14 are really efficient, the problems twirl and twist and withstand many a~brave
  15 attempt at the optimum solution. They also reveal a~vast and diverse landscape
  16 of a~deep and beautiful theory. Still closer, this landscape turns out to be interwoven
  17 with the intricate details of various models of computation and even of arithmetics
  18 itself.
  19
  20 I have tried to cover all known important results on both problems and unite them
  21 in a~single coherent theory. At many places, I have attempted to contribute my own
  22 little stones to this mosaic: several new results, simplifications of existing
  23 ones, and last, but not least filling in important details where the original
  24 authors have missed some.
  25
  26 When compared with the earlier surveys on the minimum spanning trees, most
  27 notably Graham and Hell \cite{graham:msthistory} and Eisner \cite{eisner:tutorial},
  28 this work adds many of the recent advances, the dynamic algorithms and
  29 also the relationship with computational models. No previous work covering
  30 the ranking problems in their entirety is known.
  31
  32 The early parts of this thesis also served as a~basis for a~course on graph
  33 algorithms which I was teaching at our faculty during years 2006 and~2007. They are
  34 included in the textbook \cite{mm:ga} which I have written for this course.
  35
  36 I~have tried to stick to the usual notation except where it was too inconvenient.
  37 Most symbols are defined at the place where they are used for the first time.
  38 To avoid piling up too many symbols at places that speak about a~single fixed graph,
  39 this graph is always called~$G$, its set of vertices and edges are denoted by $V$
  40 and~$E$ respectively, and I~also use~$n$ for the number of its vertices and $m$~for
  41 the number of edges. At places where there could be a~danger of confusion, more explicit notation
  42 is used instead.
  43
  44 \chapter{Minimum Spanning Trees}
  45
  46 \section{The Problem}
  47
  48 The problem of finding a minimum spanning tree of a weighted graph is one of the
  49 best studied problems in the area of combinatorial optimization since its birth.
  50 Its colorful history (see \cite{graham:msthistory} and \cite{nesetril:history} for the full account)
  51 begins in~1926 with the pioneering work of Bor\o{u}vka
  52 \cite{boruvka:ojistem}\foot{See \cite{nesetril:boruvka} for an English translation with commentary.},
  53 who studied primarily an Euclidean version of the problem related to planning
  54 of electrical transmission lines (see \cite{boruvka:networks}), but gave an efficient
  55 algorithm for the general version of the problem. As it was well before the dawn of graph
  56 theory, the language of his paper was complicated, so we will better state the problem
  57 in contemporary terminology:
  58
  59 \proclaim{Problem}Given an undirected graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$,
  60 find its minimum spanning tree, defined as follows:
  61
  62 \defn\id{mstdef}%
  63 For a given graph~$G$ with weights $w:E(G)\rightarrow {\bb R}$:
  64 \itemize\ibull
  65 \:A~subgraph $H\subseteq G$ is called a \df{spanning subgraph} if $V(H)=V(G)$.
  66 \:A~\df{spanning tree} of~$G$ is any spanning subgraph of~$G$ that is a tree.
  67 \:For any subgraph $H\subseteq G$ we define its \df{weight} $w(H):=\sum_{e\in E(H)} w(e)$.
  68   When comparing two weights, we will use the terms \df{lighter} and \df{heavier} in the
  69   obvious sense.
  70 \:A~\df{minimum spanning tree (MST)} of~$G$ is a spanning tree~$T$ such that its weight $w(T)$
  71   is the smallest possible among all the spanning trees of~$G$.
  72 \:For a disconnected graph, a \df{(minimum) spanning forest (MSF)} is defined as
  73   a union of (minimum) spanning trees of its connected components.
  74 \endlist
  75
  76 Bor\o{u}vka's work was further extended by Jarn\'\i{}k \cite{jarnik:ojistem}, again in
  77 mostly geometric setting. He has discovered another efficient algorithm. However, when
  78 computer science and graph theory started forming in the 1950's and the
  79 spanning tree problem was one of the central topics of the flourishing new
  80 disciplines, the previous work was not well known and the algorithms had to be
  81 rediscovered several times.
  82
  83 In the next 50 years, several significantly faster algorithms were discovered, ranging
  84 from the $\O(m\timesbeta(m,n))$ time algorithm by Fredman and Tarjan \cite{ft:fibonacci},
  85 over algorithms with inverse-Ackermann type complexity by Chazelle \cite{chazelle:ackermann}
  86 and Pettie \cite{pettie:ackermann}, to an~algorithm by Pettie \cite{pettie:optimal}
  87 whose time complexity is provably optimal.
  88
  89 \chapter{Bibliography}
  90
  91 \dumpbib
  92
  93 \vfill\eject
  94 \ifodd\pageno\else\hbox{}\fi
  95
  96 \bye