From 3ce379fec86d6348c80aa1d8c77fb64a0dbada13 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 23 Apr 2008 11:00:01 +0200 Subject: [PATCH] More of the prolog. --- biblio.bib | 24 +++++++++++++++++++++++- pref.tex | 36 +++++++++++++++++++++++++++++------- 2 files changed, 52 insertions(+), 8 deletions(-) diff --git a/biblio.bib b/biblio.bib index 9e56920..3311556 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1362,7 +1362,8 @@ title={{Dynamick\'e grafov\'e algoritmy}}, author={Martin Mare\v{s}}, school={Charles University in Prague, Faculty of Math and Physics}, - year={2000} + year={2000}, + notes={In Czech} } @techreport{ henzinger:twoec, @@ -1547,3 +1548,24 @@ year={1992}, publisher={Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA} } + +@techreport { mm:ga, + author = "Martin Mare\v{s}", + title = "{Krajinou grafov\'ych algoritm\accent23u}", + institution = "Institut Teoretick\'e Informatiky", + address = "Praha, Czech Republic", + year = "2007", + number = "2007--330", + type = "ITI series", + note = {In Czech}, +} + +@book { horak:mofivefour, + author = {Hor\'ak, Karel and Mare\v{s}, Martin and Novotn\'y, Peter and \v{S}im\v{s}a, Jarom\'\i{}r and \v{S}vr\v{c}ek, Jaroslav and T\"opfer, Pavel and Zhouf, Jaroslav}, + title = {54.~ro\v{c}n\'\i{}k matematick\'e olympi\'ady na st\v{r}edn\'\i{}ch \v{s}kol\'ach}, + publisher = {Jednota \v{c}esk\'ych matematik\accent23u a fyzik\accent23u}, + address = {Praha}, + year = {2007}, + note = {In Czech}, + isbn = {80-7015-109-9}, +} diff --git a/pref.tex b/pref.tex index 597430f..b5570f9 100644 --- a/pref.tex +++ b/pref.tex @@ -26,11 +26,13 @@ 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} +The early parts of this thesis also served as a~basis for the course on graph +algorithms which I was teaching at our faculty during 2006 and~2007. They are +included in the textbook \cite{mm:ga} which I have written for this course. -\def\ss#1{\medskip\>{\bo #1.}\enspace\eatspaces} +\def\ss#1{\medskip\>{\bo #1}\enspace\eatspaces} -\ss{My results} +\ss{My original results} \itemize\ibull \:The lower bound in Section \ref{contalg}. Not published yet. @@ -39,9 +41,8 @@ the ranking problems in entirety is known. \: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 ranking algorithms in Sections \ref{ranksect} to \ref{kpranksect} are results of joint research with Milan Straka. + Published in \cite{mm:rank}. \:The remaining sections of Chapter \ref{rankchap} contain unpublished original research. \endlist @@ -49,12 +50,33 @@ the ranking problems in entirety is known. \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 +\:The unified view of vector computations in Section \ref{bitsect}. Published + in the textbook \cite{mm:ga}. The main ideas of this section were also published + in the yearbook of the Czech Mathematical Olympiad \cite{horak:mofivefour}. \:Several simplifications of the soft heaps in Section \ref{shsect}. +\:The dynamic MST algorithm for graphs with limited edge weights in Section \ref{dynmstsect}. \endlist +\vfill\eject + \ss{Acknowledgements} +First of all, I~would like to thank my supervisor, Jaroslav Ne\v{s}et\v{r}il, for +introducing me to the world of discrete mathematics and gently guiding my attempts +to explore it with his deep insight. I~am very grateful to all members of the +Department of Applied Mathematics and of the Institute for Theoretical Computer +Science for the work environment which was both friendly and highly inspiring. +I~also send my acknowledgements to the members of the Math department at ETH Z\"urich and of DIMACS +at the Rutgers University (especially to J\'anos Koml\'os) where I~spent several +pleasant months working on what finally become a~part of this thesis. + +I~also thank to my family for supporting me during the plentiful years of my study, +to my girlfriend Ani\v{c}ka for lots of patience when I~was caught by my work and +hardly speaking, to all the polar bears of Kobylisy for their furry presence, and +finally to our cats Minuta and Dami\'an for their mastership in hiding my +papers, which has frequently forced me to think of new ways of looking at problems +when the old ones were impossible to find. + \ss{Notation} \bigskip -- 2.39.5