From b4ec539791b595f64d064b80054e7ac7c311aaf4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Wed, 16 Apr 2008 18:44:09 +0200 Subject: [PATCH] Converting remarks to named paragraphs. --- PLAN | 2 +- adv.tex | 24 +++++++++++++----------- macros.tex | 2 +- mst.tex | 4 ++-- ram.tex | 14 +++++++------- 5 files changed, 24 insertions(+), 22 deletions(-) diff --git a/PLAN b/PLAN index 4b0f217..8495bd6 100644 --- a/PLAN +++ b/PLAN @@ -62,6 +62,7 @@ Spanning trees: - rename theorem on Minimality by order - introduce Cut rule and Cycle rule earlier - Lemma: deletion of a non-MST edge does not alter the MST +- use the name "Boruvka step" Related: - practical considerations: katriel:cycle, moret:practice (mention pairing heaps) @@ -110,6 +111,5 @@ Notation: Varia: - cite GA booklet -- minimize the use of Remarks, use \paran instead - formatting of multi-line \algin, \algout - each chapter should make clear in which model we work diff --git a/adv.tex b/adv.tex index 604f6b1..3b1e7ed 100644 --- a/adv.tex +++ b/adv.tex @@ -124,8 +124,10 @@ $G$~would contain a~subdivision of~$K_x$ and hence $K_x$ as a~minor. \qed \rem -Minor-closed classes share many other interesting properties, as shown for -example by Theorem 6.1 of \cite{nesetril:minors}. +Minor-closed classes share many other interesting properties, for example bounded chromatic +numbers of various kinds, as shown by Theorem 6.1 of \cite{nesetril:minors}. + +Let us return to the analysis of our algorithm. \thmn{MST on minor-closed classes \cite{mm:mst}}\id{mstmcc}% For any fixed non-trivial minor-closed class~$\cal C$ of graphs, the Contractive Bor\o{u}vka's @@ -144,7 +146,7 @@ but followed by flattening, so they are equivalent to contractions on simple gra So they also belong to~$\cal C$ and by the previous theorem $m_i\le \varrho({\cal C})\cdot n_i$. \qed -\rem\id{nobatch}% +\paran{Local contractions}\id{nobatch}% The contractive algorithm uses ``batch processing'' to perform many contractions in a single step. It is also possible to perform contractions one edge at a~time, batching only the flattenings. A~contraction of an edge~$uv$ can be done @@ -171,7 +173,7 @@ random. Then $\E X \le 2\varrho$, hence by the Markov's inequality ${\rm Pr}[X > 4\varrho] < 1/2$, so for at least $n/2$ vertices~$v$ we have $\deg(v)\le 4\varrho$. -\algn{Local Bor\o{u}vka's Algorithm \cite{mm:mst}}% +\algn{Local Bor\o{u}vka's Algorithm, Mare\v{s} \cite{mm:mst}}% \algo \algin A~graph~$G$ with an edge comparison oracle and a~parameter~$t\in{\bb N}$. \:$T\=\emptyset$. @@ -222,7 +224,7 @@ Bor\o{u}vka's Algorithm (see \ref{contiter}). The whole algorithm therefore runs in time $\O(\sum_i m_i) = \O(\sum_i n/2^i) = \O(n)$. \qed -\rem +\paran{Back to planar graphs}% For planar graphs, we can get a sharper version of the low-degree lemma, showing that the algorithm works with $t=8$ as well (we had $t=12$ as $\varrho=3$). While this does not change the asymptotic time complexity @@ -257,7 +259,7 @@ has degree~9. \figure{hexangle.eps}{\epsfxsize}{The construction from Remark~\ref{hexa}} \rem -The observation in~Theorem~\ref{mstmcc} was also made by Gustedt in~\cite{gustedt:parallel}, +The observation in~Theorem~\ref{mstmcc} was also independently made by Gustedt in~\cite{gustedt:parallel} who studied a~parallel version of the contractive Bor\o{u}vka's algorithm applied to minor-closed classes. @@ -344,7 +346,7 @@ thus by the previous theorem the operations take $\O(m+n\log n)$ time in total. \cor For graphs with edge density at least $\log n$, this algorithm runs in linear time. -\rem +\remn{Other heaps}% We can consider using other kinds of heaps that have the property that inserts and decreases are faster than deletes. Of course, the Fibonacci heaps are asymptotically optimal (by the standard $\Omega(n\log n)$ lower bound on sorting by comparisons, see @@ -368,7 +370,7 @@ queues described in \cite{thorup:pqsssp} which have constant-time \ and and $\O(\log\log n)$ time \. (We will however omit the details since we will show a~faster integer algorithm soon.) -\para +\paran{Combining MST algorithms}% As we already noted, the improved Jarn\'\i{}k's algorithm runs in linear time for sufficiently dense graphs. In some cases, it is useful to combine it with another MST algorithm, which identifies a~part of the MST edges and contracts @@ -398,7 +400,7 @@ $m'\le m$ and $n'\le n/\log n$. The second step then runs in time $\O(m'+n'\log and both trees can be combined in linear time, too. \qed -\para +\paran{Iterating Jarn\'\i{}k's algorithm}% Actually, there is a~much better choice of the algorithms to combine: use the Active Edge Jarn\'\i{}k's algorithm multiple times, each time stopping after a~while. A~good choice of the stopping condition is to place a~limit on the size of the heap. @@ -568,7 +570,7 @@ to $w(uv)$. It is therefore sufficient to solve the following problem: Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] ; u,v\in V(T) \}$ specified by their endpoints, find the heaviest edge (\df{peak}) for every path in~$Q$. -\para +\paran{Bor\o{u}vka trees}% Finding the peaks can be burdensome if the tree~$T$ is degenerated, so we will first reduce it to the same problem on a~balanced tree. We run the Bor\o{u}vka's algorithm on~$T$, which certainly produces $T$ itself, and we @@ -648,7 +650,7 @@ and split the path by the two half-paths. This produces a~set~$Q'$ of at most~$2 The peak of every original query path is then the heavier of the peaks of its halves. \qed -\para +\paran{Bounding comparisons}% We will now describe a~simple variant of the depth-first search which finds the peaks of all query paths of the transformed problem. As we promised, we will take care of the number of comparisons only, as long as all other operations diff --git a/macros.tex b/macros.tex index 52b2835..9dba90d 100644 --- a/macros.tex +++ b/macros.tex @@ -377,7 +377,7 @@ \def\problemn{\problem\labelx} \def\remn{\rem\labelx} -\def\paran#1{\para {\sl #1:\/}\enspace} +\def\paran#1{\para {\sl #1.\/}\enspace} \def\proof{\noindent {\sl Proof.}\enspace} \def\proofsketch{\noindent {\sl Proof sketch.}\enspace} diff --git a/mst.tex b/mst.tex index 963e068..929f783 100644 --- a/mst.tex +++ b/mst.tex @@ -640,7 +640,7 @@ in section~\ref{minorclosed}. To achieve the linear time complexity, the algorithm needs a very careful implementation, but we defer the technical details to section~\ref{bucketsort}. -\para +\paran{General contractions}% Graph contractions are indeed a~very powerful tool and they can be used in other MST algorithms as well. The following lemma shows the gist: @@ -667,7 +667,7 @@ which obviously works in multigraphs as well.) \rem In the previous algorithm, the role of the mapping~$\pi^{-1}$ is of course played by the edge labels~$\ell$. -\para +\paran{A~lower bound}% Finally, we will show a family of graphs where the $\O(m\log n)$ bound on time complexity is tight. The graphs do not have unique weights, but they are constructed in a way that the algorithm never compares two edges with the same weight. Therefore, when two such diff --git a/ram.tex b/ram.tex index 6691434..61db822 100644 --- a/ram.tex +++ b/ram.tex @@ -860,8 +860,8 @@ Q-heaps of size $k=\log^{1/4} N$, where $N$ is the size of the algorithm's input This guarantees that $k\le W^{1/4}$ and $\O(2^{k^4}) = \O(N)$. Let us however remark that the whole construction is primarily of theoretical importance and that the huge constants involved everywhere make these heaps useless -in practical algorithms. Many of the tricks used however prove themselves -useful even in real-life implementations. +in practical algorithms. Despise this, many of the tricks we develop have proven +themselves useful even in real-life implementations. Spending the time on reprocessing makes it possible to precompute tables for almost arbitrary functions and then assume that they can be evaluated in @@ -877,7 +877,7 @@ them we spend $\poly(k)$ time on calculating the function. It remains to observe that $2^{\O(k^3)}\cdot \poly(k) = \O(2^{k^4})$. \qed -\para +\paran{Tries and ranks}% We will first show an~auxiliary construction based on tries and then derive the real definition of the Q-heap from it. @@ -908,7 +908,7 @@ A~\df{compressed trie} is obtained from the trie by removing the vertices of out except for the root and marked vertices. Whereever is a~directed path whose internal vertices have outdegree~1 and they carry no mark, we replace this path by a~single edge labeled with the contatenation -of the original edge's labels. +of the original edges' labels. In both kinds of tries, we order the outgoing edges of every vertex by their labels lexicographically. @@ -978,7 +978,7 @@ all values in that subtree have $x_j[b]=1$ and thus they are larger than~$x$. In case, $x[b]=1$ and $x_j[b]=0$, so they are smaller. \qed -\para +\paran{A~better representation}% The preceding lemma shows that the rank can be computed in polynomial time, but unfortunately the variables on which it depends are too large for a~table to be efficiently precomputed. We will carefully choose an~equivalent representation @@ -1129,7 +1129,7 @@ A~\df{Q-heap} consists of: \algout The $i$-th smallest element in the heap. \endalgo -\para +\paran{Extraction}% The heap algorithms we have just described have been built from primitives operating in constant time, with one notable exception: the extraction $x[B]$ of all bits of~$x$ at positions specified by the set~$B$. This cannot be done @@ -1178,7 +1178,7 @@ logarithms and bit extraction. All these can be calculated in constant time using the results of section \ref{bitsect} and Lemma \ref{qhxtract}. \qed -\rem +\paran{Combining Q-heaps}% We can also use the Q-heaps as building blocks of more complex structures like Atomic heaps and AF-heaps (see once again \cite{fw:transdich}). We will show a~simpler, but useful construction, sometimes called the \df{Q-heap tree.} -- 2.39.5