X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=appl.tex;h=1b3b3da86058f8a3487de91bdb58eaf81419e364;hb=fa37f59e9f5767013d0bf6678544dc1e79159725;hp=82c2a1a9918d0e6e3c28456bb3c9a74edfdfac39;hpb=1e0055d9c1ccd9dccba79f5bb64f4f558efc74e1;p=saga.git

diff --git a/appl.tex b/appl.tex
index 82c2a1a..1b3b3da 100644
--- a/appl.tex
+++ b/appl.tex
@@ -144,4 +144,52 @@ There is also a~$\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.)
 
+%--------------------------------------------------------------------------------
+
+\section{Practical algorithms}
+
+So far, we were studying the theoretical aspects of the MST algorithms.
+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
+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.
+
+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
+and minor-closed classes.
+
+Also, Katriel et al.~\cite{katriel:cycle} have proposed a~new algorithm based on~the
+Red rule. It is a~randomized algorithm which uses a~simplified form of the idea of edge
+filtering from the algorithm of Karger, Klein and Tarjan (see Section \ref{randmst}).
+The expected time complexity is slightly worse: $\O(n\log n + m)$. However, for dense
+graphs it performs very well in practice, even in comparison with the Moret's results.
+
+\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.
+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).
+
+Several better algorithms have been constructed, the best of which run in time $\O(\log n)$.
+Chong, Han and Lam \cite{chong:parallel} have recently discovered an~algorithm that achieves
+this time complexity even on the EREW PRAM --- the weakest of the parallel RAM's which does
+not allow concurrent reading nor writing to the same memory cell by multiple processors.
+In this model, the $\O(\log n)$ bound is clearly the best possible.
+
+As in the sequential models, the basic question still remains open: Is it
+possible to compute the MST in parallel on EREW PRAM, spending only linear
+work? This would of course imply existence of a~linear-time sequential
+algorithm, so none of the known parallel algorithms achieve that. Algorithms
+with linear work can be obtained by utilizing randomness, as shown for example
+by Pettie and Ramachandran \cite{pettie:minirand}, but so far only at the
+expense of higher time complexity.
+
 \endpart