From fa37f59e9f5767013d0bf6678544dc1e79159725 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sun, 20 Apr 2008 21:49:50 +0200 Subject: [PATCH] Practical and parallel algorithms. --- PLAN | 10 +++------- appl.tex | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ biblio.bib | 41 ++++++++++++++++++++++++++++++++++++++++- macros.tex | 2 +- 4 files changed, 92 insertions(+), 9 deletions(-) diff --git a/PLAN b/PLAN index 41930d0..81d21f3 100644 --- a/PLAN +++ b/PLAN @@ -60,13 +60,9 @@ Spanning trees: - Some algorithms (most notably Fredman-Tarjan) do not need flattening - use the notation for contraction by a set - mention bugs in Valeria's verification paper -- more references on decision trees -- Lemma: deletion of a non-MST edge does not alter the MST -- mention that there are only a few algorithms based on the Red rule +* Lemma: deletion of a non-MST edge does not alter the MST Related: -- practical considerations: katriel:cycle, moret:practice (mention pairing heaps) -- parallel algorithms: p243-cole (see also remarks in Karger and pettie:minirand), pettie:parallel - K best trees - degree-restricted cases and arborescences - bounded expansion classes? @@ -86,10 +82,10 @@ Notation: - sort the table - G has to be connected, so m=O(n) -- impedance mismatch in terminology: contraction of G along e vs. contraction of e. +* impedance mismatch in terminology: contraction of G along e vs. contraction of e. - use \delta(X) notation - unify use of n(G) vs. n -- change the notation for contractions -- use double slash instead of the dot? +* change the notation for contractions -- use double slash instead of the dot? - introduce \widehat\O early Typography: 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 diff --git a/biblio.bib b/biblio.bib index 3e75568..9e56920 100644 --- a/biblio.bib +++ b/biblio.bib @@ -1495,7 +1495,7 @@ pages = {247--255}, } -@article{375847, +@article{ chong:parallel, author = {Ka Wong Chong and Yijie Han and Tak Wah Lam}, title = {Concurrent threads and optimal parallel minimum spanning trees algorithm}, journal = {Journal of the ACM}, @@ -1508,3 +1508,42 @@ publisher = {ACM}, address = {New York, NY, USA}, } + +@article{ moret:expmst, + title={{An Empirical Assessment of Algorithms for Constructing a Minimum Spanning Tree}}, + author={Moret, B. M. E. and Shapiro, H. D.}, + journal={Computational Support for Discrete Mathematics: DIMACS Workshop, March 12-14, 1992}, + year={1994}, + publisher={American Mathematical Society} +} + +@article{ fredman:pairingheap, + title={{The pairing heap: A new form of self-adjusting heap}}, + author={Fredman, M.L. and Sedgewick, R. and Sleator, D.D. and Tarjan, R.E.}, + journal={Algorithmica}, + volume={1}, + number={1}, + pages={111--129}, + year={1986}, + publisher={Springer} +} + +@article{ pettie:pairing, + author = {Seth Pettie}, + title = {Towards a Final Analysis of Pairing Heaps}, + journal = {focs}, + volume = {00}, + year = {2005}, + isbn = {0-7695-2468-0}, + pages = {174-183}, + doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75}, + publisher = {IEEE Computer Society}, + address = {Los Alamitos, CA, USA}, +} + +@book{ jaja:parallel, + title={{An introduction to parallel algorithms}}, + author={J{\'a}J{\'a}, J.}, + year={1992}, + publisher={Addison Wesley Longman Publishing Co., Inc. Redwood City, CA, USA} +} diff --git a/macros.tex b/macros.tex index 5877aba..3a734d8 100644 --- a/macros.tex +++ b/macros.tex @@ -384,7 +384,7 @@ \def\problemn{\problem\labelx} \def\remn{\rem\labelx} -\def\paran#1{\para {\sl #1.\/}\enspace} +\def\paran#1{\para {\sl #1.\/}\enspace\kern 0pt} \def\proof{\noindent {\sl Proof.}\enspace} \def\proofsketch{\noindent {\sl Proof sketch.}\enspace} -- 2.39.2