X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=appl.tex;h=f9d59ab811f3b882a21ea55de4c806c207036047;hb=124f193d14bed24539c5cd59407637cc38dbe740;hp=13455b1426830dc7fe66b1e55bce17c22950b53a;hpb=55c1a7d3c5c439a7475393dba7a1bef73e4f583e;p=saga.git diff --git a/appl.tex b/appl.tex index 13455b1..f9d59ab 100644 --- a/appl.tex +++ b/appl.tex @@ -7,13 +7,13 @@ \section{Special cases and related problems} Towards the end of our story of the minimum spanning trees, we will now focus our attention -on various special cases of our problem and also to several related problems that +on various special cases of the MST problem and also to several related problems that frequently arise in practice. -\paran{Graphs with sorted edges} +\paran{Graphs with sorted edges}\id{sortededges}% When the edges of the given graph are already sorted by their weights, we can use the Kruskal's algorithm to find the MST in time $\O(m\timesalpha(n))$ (Theorem \ref{kruskal}). -We however can do better: As the minimality of a~spanning tree depends only on the +We can however do better: As the minimality of a~spanning tree depends only on the order of weights and not on the actual values (The Minimality Theorem, \ref{mstthm}), we can renumber the weights to $1, \ldots, m$ and find the MST using the Fredman-Willard algorithm for integer weights. According to Theorem \ref{intmst} it runs in @@ -40,8 +40,8 @@ the order of these integers is the same as of the original FP numbers. We can therefore once again replace the edge weights by integers and use the linear-time integer algorithm. While the other FP representations (see \cite{dgoldberg:fp} for an~overview) need not have this property, the corresponding integers can be adjusted -in $\O(1)$ time to the format we need. (More advanced tricks of this type have been -employed by Thorup in \cite{thorup:floatint} to extend his linear-time algorithm +in $\O(1)$ time to the format we need using bit masking. (More advanced tricks of this type have been +employed by Thorup \cite{thorup:floatint} to extend his linear-time algorithm for single-source shortest paths to FP edge lengths.) \paran{Graphs with bounded degrees} @@ -69,9 +69,10 @@ obvious from the Kruskal's algorithm) and as~$G$ can be obtained from the new~$G'$ by contracting the path, the rest follows from the Contraction lemma (\ref{contlemma}). -This step can be carried out in time $\O(d)$. As it replaces a high-degree -vertex by vertices of degree~3, the whole procedure stops in at most~$n$ such -steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$ including the +This step can be carried out in time $\O(d)$. It replaces a high-degree +vertex by vertices of degree~3 and it does not change degrees of any other +vertices. So the whole procedure stops in at most~$n$ such +steps, so it takes time $\O(\sum_{v\in V}\deg(v)) = \O(m)$, including the time needed to find the high-degree vertices at the beginning. \qed @@ -87,7 +88,7 @@ in time $\O(n^2)$. There is a~more efficient method based on the observation that the MST is always a~subgraph of the Delaunay's tesselation for the given points -(this was first noted by Shamos and Hoey in~\cite{shamos:closest}). The +(this was first noted by Shamos and Hoey \cite{shamos:closest}). The tesselation is a~planar graph, which guarantees that it has $\O(n)$ edges, and it is a~dual graph of the Voronoi diagram of the given points, which can be constructed in time $\O(n\log n)$ using for example the Fortune's @@ -102,6 +103,10 @@ based on the sweep-line technique and the Red rule. For other variations on the geometric MST, see Eppstein's survey paper \cite{eppstein:spanning}. +There are also plentiful interesting results on expected properties of the +Euclidean MST of various random point configurations. These are well covered +by the monographs of Steele \cite{steele:ptco} and Yukich \cite{yukich:pteucl}. + \paran{Steiner trees} The constraint that the segments in the previous example are allowed to touch each other only in the given points looks artificial and it is indeed uncommon in @@ -112,14 +117,14 @@ Jacob Steiner who studied a~special case of this problem in the 19th century.} We can also define it in terms of graphs: \defn A~\df{Steiner tree} of a~weighted graph~$(G,w)$ with a~set~$M\subseteq V$ -of \df{mandatory notes} is a~tree~$T\subseteq G$ that contains all the mandatory +of \df{mandatory vertices} is a~tree~$T\subseteq G$ that contains all the mandatory vertices and its weight is minimum possible. -For $M=V$ the Steiner tree is identical to the MST, but if we allow an~arbitrary +When $M=V$, the Steiner tree is identical to the MST, but if we allow an~arbitrary choice of the mandatory vertices, it is NP-hard. This has been proven by Garey and Johnson \cite{garey:steiner,garey:rectisteiner} for not only the graph version with weights $\{1,2\}$, but also for the planar version with Euclidean or rectilinear -metric. There is a~polynomial approximation algorithm with ratio $5/3$ for +metric. There is a~polynomial-time approximation algorithm with ratio $5/3$ for graphs due to Pr\"omel and Steger \cite{proemel:steiner} and a~polynomial-time approximation scheme for the Euclidean Steiner tree in an~arbitrary dimension by Arora \cite{arora:tspapx}. @@ -132,7 +137,7 @@ have shown an~algorithm which, given $0 < \varepsilon < 1/2$, approximates the weight of the MST of a~graph with average degree~$d$ and edge weights from the set $\{1,\ldots,w\}$ in time $\O(dw\varepsilon^{-2}\cdot\log(dw/\varepsilon))$, producing a~weight which has relative error at most~$\varepsilon$ with probability -at least $3/4$. They have also proven an~almost matching lower bound $\Omega(dw\varepsilon^{-2})$. +at least $3/4$. They have also proven a~close lower bound $\Omega(dw\varepsilon^{-2})$. For the $d$-dimensional Euclidean case, there is a~randomized approximation algorithm by Czumaj et al.~\cite{czumaj:euclidean} which with high probability @@ -140,7 +145,7 @@ produces a~spanning tree within relative error~$\varepsilon$ in $\widetilde\O(\s $\widetilde\O(f) = \O(f\cdot\log^{\O(1)} f)$ and $\poly(n)=n^{\O(1)}$.} queries to a~data structure containing the points. The data structure is expected to answer orthogonal range queries and cone approximate nearest neighbor queries. -There is also a~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation +There is also an~$\widetilde\O(n\cdot \poly(1/\varepsilon))$ time approximation algorithm for the MST weight in arbitrary metric spaces by Czumaj and Sohler \cite{czumaj:metric}. (This is still sub-linear since the corresponding graph has roughly $n^2$ edges.) @@ -154,13 +159,13 @@ How should we find the MST on a~real computer? Moret and Shapiro \cite{moret:expmst} have conducted an~extensive experimental study of performance of implementations of various MST algorithms on different computers. They have tested the algorithms on several sets of graphs, varying -in the number of vertices (up to millions) and edge density (from constant to -$n^{1/2}$. In almost all tests, the quickest algorithm was an~ordinary Prim's +in the number of vertices (up to millions) and in edge density (from constant to +$n^{1/2}$. In almost all tests, the winner was an~ordinary Prim's algorithm implemented with pairing heaps \cite{fredman:pairingheap}. The pairing heaps are known to perform surprisingly well in practice, but they still elude attempts at complete theoretical analysis. So far the best results are those of Pettie \cite{pettie:pairing}, who has proven that deletion of the minimum takes $\O(\log n)$ -time and all other operations $\O(2^{2\scriptscriptstyle\sqrt{\log\log n}})$; both bounds are amortized. +time and all other operations take $\O(2^{2\scriptscriptstyle\sqrt{\log\log n}})$; both bounds are amortized. The Moret's study however completely misses variants of the Bor\o{u}vka's algorithm and many of those have very promising characteristics, especially for planar graphs @@ -174,7 +179,7 @@ graphs it performs very well in practice, even in comparison with the Moret's re \paran{Parallel algorithms} Most of the early parallel algorithms for the MST are variants of the Bor\o{u}vka's algorithm. -The operations on the individual trees are independent of each other, so they can run in parallel. +The operations on the individual trees are independent of each other, so they can be carried out in parallel. There are $\O(\log n)$ steps and each of them can be executed in $\O(\log n)$ parallel time using standard PRAM techniques (see \cite{jaja:parallel} for the description of the model).