pref.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \unchapter{Preface}
   6
   7 This thesis tells the story of two well-established problems of algorithmic
   8 graph theory: the minimum spanning trees and ranks of permutations. At distance,
   9 both problems seem to be simple, boring and already solved, because we have poly\-nom\-ial-time
  10 algorithms for them since ages. But when we come closer and seek algorithms that
  11 are really efficient, the problems twirl and twist and withstand many a~brave
  12 attempt at the optimum solution. They also reveal a~vast and diverse landscape
  13 of a~deep and beautiful theory. Still closer, this landscape turns out to be interwoven
  14 with the intricate details of various models of computation and even of arithmetics
  15 itself.
  16
  17 I have tried to cover all known important results on both problems and unite them
  18 in a~single coherent theory. At many places, I have tried to contribute my own
  19 little stones to this mosaic: several new results, simplifications of existing
  20 ones, and last, but not least filling in important details where the original
  21 authors have missed some.
  22
  23 When compared with the earlier surveys on the minimum spanning trees, most
  24 notably Graham and Hell \cite{gh:history} and Eisner \cite{eisner:tutorial},
  25 this work includes many of the recent advances, the dynamic algorithms and
  26 also the relationship with computational models. No previous work covering
  27 the ranking problems in entirety is known.
  28
  29 \FIXME{GA booklet}
  30
  31 \def\ss#1{\medskip\>{\bo #1.}\enspace\eatspaces}
  32
  33 \ss{My results}
  34
  35 \itemize\ibull
  36 \:The lower bound in Section \ref{contalg}. Not published yet.
  37 \:The tree isomorphism algorithm in Section \ref{bucketsort}. Not published yet.
  38 \:Both algorithms for minor-closed graph classes in Section \ref{minorclosed}. Published in \cite{mm:mst}.
  39 \:The linear-time verification algorithm in Section \ref{verifysect} is a~simplification
  40   of the algorithm of King \cite{king:verify} and it corrects many omissions
  41   in the original paper. Not published yet.
  42 \:The dynamic MST algorithm for graphs with limited edge weights in Section \ref{dynmstsect}.
  43 \:The ranking algorithms in Sections \ref{ranksect} to \ref{kpranksect} are joint research with Milan Straka,
  44   published in \cite{mm:rank}.
  45 \:The remaining sections of Chapter \ref{rankchap} contain unpublished original research.
  46 \endlist
  47
  48 \ss{Other minor contributions}
  49
  50 \itemize\ibull
  51 \:The flattening procedure in Section \ref{bucketsort}. Published in \cite{mm:mst}.
  52 \:The unified view of vector computations in Section \ref{bitsect}. XXXX: MO
  53 \:Several simplifications of the soft heaps in Section \ref{shsect}.
  54 \endlist
  55
  56 \ss{Acknowledgements}
  57
  58 \ss{Notation}
  59
  60 \bigskip
  61
  62 So, my gentle reader, let us nestle deep in an~ancient wing armchair. The saga of the
  63 graph algorithms begins~\dots
  64
  65 \endpart