Parts of preface.

[saga.git] / pref.tex

diff --git a/pref.tex b/pref.tex
index 5597cc5539c1a3744eb76ce65317e8ec96434295..597430ffb375e6ef515795bed6c8aaf71629bd07 100644 (file)
--- a/pref.tex
+++ b/pref.tex
@@ -4,4 +4,62 @@
 
 \unchapter{Preface}
 
+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 tried 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{gh:history} and Eisner \cite{eisner:tutorial},
+this work includes many of the recent advances, the dynamic algorithms and
+also the relationship with computational models. No previous work covering
+the ranking problems in entirety is known.
+
+\FIXME{GA booklet}
+
+\def\ss#1{\medskip\>{\bo #1.}\enspace\eatspaces}
+
+\ss{My results}
+
+\itemize\ibull
+\:The lower bound in Section \ref{contalg}. Not published yet.
+\:The tree isomorphism algorithm in Section \ref{bucketsort}. Not published yet.
+\:Both algorithms for minor-closed graph classes in Section \ref{minorclosed}. Published in \cite{mm:mst}.
+\:The linear-time verification algorithm in Section \ref{verifysect} is a~simplification
+  of the algorithm of King \cite{king:verify} and it corrects many omissions
+  in the original paper. Not published yet.
+\:The dynamic MST algorithm for graphs with limited edge weights in Section \ref{dynmstsect}.
+\:The ranking algorithms in Sections \ref{ranksect} to \ref{kpranksect} are joint research with Milan Straka,
+  published in \cite{mm:rank}.
+\:The remaining sections of Chapter \ref{rankchap} contain unpublished original research.
+\endlist
+
+\ss{Other minor contributions}
+
+\itemize\ibull
+\:The flattening procedure in Section \ref{bucketsort}. Published in \cite{mm:mst}.
+\:The unified view of vector computations in Section \ref{bitsect}. XXXX: MO
+\:Several simplifications of the soft heaps in Section \ref{shsect}.
+\endlist
+
+\ss{Acknowledgements}
+
+\ss{Notation}
+
+\bigskip
+
+So, my gentle reader, let us nestle deep in an~ancient wing armchair. The saga of the
+graph algorithms begins~\dots
+
 \endpart