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 attempted 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{graham:msthistory} and Eisner \cite{eisner:tutorial},
  25 this work adds 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 their entirety is known.
  28
  29 The early parts of this thesis also served as a~basis for a~course on graph
  30 algorithms which I was teaching at our faculty during years 2006 and~2007. They are
  31 included in the textbook \cite{mm:ga} which I have written for this course.
  32
  33 \def\ss#1{\medskip\>{\bo #1}\enspace\eatspaces}
  34
  35 \ss{My original results}
  36
  37 \itemize\ibull
  38 \:The lower bound in Section \ref{contalg}. Not published yet.
  39 \:The tree isomorphism algorithm in Section \ref{bucketsort}. Not published yet.
  40 \:One of the algorithms for minor-closed graph classes in Section \ref{minorclosed}. Published in \cite{mm:mst}.
  41 \:The linear-time verification algorithm in Section \ref{verifysect} is a~simplification
  42   of the algorithm of King \cite{king:verifytwo} and it corrects many omissions
  43   in the original paper. Not published yet.
  44 \:The ranking algorithms in Sections \ref{ranksect} to \ref{kpranksect} are results of joint research with Milan Straka.
  45   Published in \cite{mm:rank}.
  46 \:The remaining sections of Chapter \ref{rankchap} contain unpublished original results.
  47 \endlist
  48
  49 \ss{Other minor contributions}
  50
  51 \itemize\ibull
  52 \:The flattening procedure in Section \ref{bucketsort}. Included in \cite{mm:mst}.
  53 \:The unified view of vector computations in Section \ref{bitsect}. Published
  54   in the textbook \cite{mm:ga}. The main ideas of this section were also included
  55   in the yearbook of the Czech Mathematical Olympiad \cite{horak:mofivefour}.
  56 \:Slight simplifications of the soft heaps and their analysis in Section \ref{shsect}.
  57 \:The dynamic MST algorithm for graphs with limited edge weights in Section \ref{dynmstsect}.
  58 \endlist
  59
  60 \vfill\eject
  61
  62 \ss{Acknowledgements}
  63
  64 First of all, I~would like to thank my supervisor, Jaroslav Ne\v{s}et\v{r}il, for
  65 introducing me to the world of discrete mathematics and gently guiding my attempts
  66 to explore it with his deep insight. I~am very grateful to all members of the
  67 Department of Applied Mathematics and the Institute for Theoretical Computer
  68 Science for the work environment which was friendly and highly inspiring.
  69 I~cannot forget the participants of the department's seminars,
  70 who have listened to my talks and provided lots of important feedback.
  71 I~also send my acknowledgements to the members of the Math department at ETH Z\"urich and of DIMACS
  72 at the Rutgers University (especially to J\'anos Koml\'os) where I~spent several
  73 pleasant months working on what finally become a~part of this thesis.
  74
  75 I~also thank to my family for supporting me during the plentiful years of my study,
  76 to my girlfriend Ani\v{c}ka for lots of patience when I~was caught up by my work and
  77 hardly speaking at all, to all the polar bears of Kobylisy for their furry presence, and
  78 finally to our cats Minuta and Dami\'an for their mastership in hiding my
  79 papers, which has frequently forced me to think of new ways of looking at problems
  80 when the old ones were impossible to find.
  81
  82 \ss{Notation}
  83
  84 I~have tried to stick to the usual notation except where it was too inconvenient.
  85 Most symbols are defined at the place where they are used for the first time.
  86 A~complete index of symbols with pointers to their definitions is then available
  87 in Appendix~\ref{notapp}. This appendix also describes the formalism of
  88 multigraphs and of the Ackermann's function, both of which are not defined
  89 consistently in the common literature.
  90
  91 To avoid piling up too many symbols at places that speak about a~single fixed graph,
  92 this graph is always called~$G$, its set of vertices and edges are denoted by $V$
  93 and~$E$ respectively, and I~also use~$n$ for the number of its vertices and $m$~for
  94 the number of edges. At places where there could be a~danger of confusion, more explicit notation
  95 is used instead.
  96
  97
  98 \bigskip
  99
 100 So, my gentle reader, let us nestle deep in an~ancient wing armchair. The saga of the
 101 graph algorithms begins~\dots
 102
 103 \endpart