\input macros.tex
+\input fonts10.tex
+
\finaltrue
\hwobble=0mm
\advance\hsize by 1cm
\advance\vsize by 20pt
-\font\chapfont=csb14 at 16pt
\def\rawchapter#1{\vensure{0.5in}\bigskip\goodbreak
\leftline{\chapfont #1}
}
\endalgo
\thm
-The Contractive Bor\o{u}vka's algorithm finds the MST of the input graph in
-time $\O(\min(n^2,m\log n))$.
+The Contractive Bor\o{u}vka's algorithm finds the MST of the graph given as
+its input in time $\O(\min(n^2,m\log n))$.
We also show that this time bound is tight --- we construct an~explicit
family of graphs on which the algorithm spends $\Theta(m\log n)$ steps.
We recursively compute the MSF of those subgraphs and of the contracted graph. Then we take the
union of these MSF's and add the corrupted edges. According to the previous lemma, this does not produce
the MSF of~$G$, but a~sparser graph containing it, on which we can continue.
+%%The following theorem describes the properties of this partition:
\thmn{Partitioning to contractible clusters, Chazelle \cite{chazelle:almostacker}}\id{partthm}%
Given a~weighted graph~$G$ and parameters $\varepsilon$ ($0<\varepsilon\le 1/2$)
The Pettie's and Ramachandran's algorithm combines the idea of robust partitioning with optimal decision
trees constructed by brute force for very small subgraphs.
-Formally, the decision trees are defined as follows:
+%%Formally, the decision trees are defined as follows:
+Let us define them first:
\defnn{Decision trees and their complexity}\id{decdef}%
A~\df{MSF decision tree} for a~graph~$G$ is a~binary tree. Its internal vertices
a~collection~$\C=\{C_1,\ldots,C_k\}$ of clusters and a~set~$R^\C$ of corrupted edges.
\:$F_i \= \mst(C_i)$ for all~$i$, obtained using optimal decision trees.
\:$G_A \= (G / \bigcup_i C_i) \setminus R^\C$. \cmt{the contracted graph}
-\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (\ref{itjar}).
+\:$F_A \= \msf(G_A)$ calculated by the Iterated Jarn\'\i{}k's algorithm (see Section \ref{iteralg}).
\:$G_B \= \bigcup_i F_i \cup F_A \cup R^\C$. \cmt{combine subtrees with corrupted edges}
\:Run two Bor\o{u}vka steps (iterations of the Contractive Bor\o{u}vka's algorithm, \ref{contbor}) on~$G_B$,
getting a~contracted graph~$G_C$ and a~set~$F_B$ of MST edges.
\dumpbib
-\vfill\eject
-
-\appendices
-
-\rawchapter{Publications of Martin Mare\v{s}}
-\medskip
-
-{
-
-\def\bibitem[#1]#2#3\par{\:\eatspaces #3}
-\def\em{\it}
-\frenchspacing
-\newcount\citecount
-\def\newblock{\hskip .11em plus .33em minus .07em }%
-\def\citelist{\numlist\singlecit\rightskip=0pt}
-\def\singlecit{\global\advance\citecount by 1[\the\citecount]}
-\hfuzz=4pt
-
-\citelist
-
-\bibitem[Mar04]{mm:mst}
-M.~Mare\v{s}.
-\newblock {Two linear time algorithms for MST on minor closed graph classes}.
-\newblock {\em {Archivum Mathematicum}}, 40:315--320. Masaryk University, Brno,
- Czech Republic, 2004.
-
-\bibitem[MS07]{mm:rank}
-M.~Mare\v{s} and M.~Straka.
-\newblock Linear-time ranking of permutations.
-\newblock In {\em Algorithms --- ESA 2007: 15th Annual European Symposium},
- volume 4698 of {\em {Lecture Notes in Computer Science}}, pages 187--193.
- Springer Verlag, 2007.
-
-\bibitem[Mar07]{mm:ga}
-M.~Mare\v{s}.
-\newblock {Krajinou grafov\'ych algoritm\accent23u (Through the Landscape of
- Graph Algorithms)}.
-\newblock ITI series 2007--330, Institut Teoretick\'e Informatiky, Praha, Czech
- Republic, 2007.
-\newblock In Czech.
-
-\bibitem[Mar00]{mares:dga}
-M.~Mare\v{s}.
-\newblock {Dynamick\'e grafov\'e algoritmy (Dynamic Graph Algorithms)}.
-\newblock Master's thesis, Charles University in Prague, Faculty of Math and
- Physics, 2000.
-\newblock In Czech.
-
-\bibitem[Mar07b]{mm:grading}
-{M. Mare\v{s}}.
-\newblock {Perspectives on Grading Systems}.
-\newblock {\em Olympiads in Informatics}, 1:124--130. Institute of
- Mathematics and Informatics, Vilnius, Lithuania, 2007.
-
-\endlist
-
-\rawsection{Citations}
-
-\citelist
-
-%S. Tazari and M. Müller-Hannemann
-%Shortest Paths in Linear Time on Minor-Closed Graph Classes with an Application to Steiner Tree Approximation (abstract)
-%submitted for publication, 2007.
-
-\bibitem[HW07]{hochstein:maxflow}
-J.~M. Hochstein and K.~Weihe.
-\newblock {Maximum $s$-$t$-flow with $k$ crossings in $\O(k^3n \log n)$ time}.
-\newblock In {\em SODA 2007: Proceedings of the 18th annual ACM-SIAM symposium
- on Discrete algorithms}, pages 843--847, 2007.
-\newblock Cites~[1].
-
-\bibitem[MHT07]{tazari:mcgc}
-M.~M\"uller-Hannemann and S.~Tazari.
-\newblock {Handling Proper Minor-Closed Graph Classes in Linear Time: Shortest
- Paths and 2-Approximate Steiner Trees}.
-\newblock Tech Report 2007/5, University of Halle-Wittenberg, Institute of
- Computer Science, 2007.
-\newblock Cites~[1].
-
-\endlist
-
-}
-
\vfill\eject
\ifodd\pageno\else\hbox{}\fi
projects / saga.git / blobdiff