de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45532

Spirakis,  P. G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45787

Zaroliagis,  Christos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-94-131.pdf
(Any fulltext), 287KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Kavvadias, G., Pantziou, G. E., Spirakis, P. G., & Zaroliagis, C.(1994). Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems (MPI-I-94-131). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B521-0
Abstract
We show how to decompose efficiently in parallel {\em any} graph into a number, $\tilde{\gamma}$, of outerplanar subgraphs (called {\em hammocks}) satisfying certain separator properties. Our work combines and extends the sequential hammock decomposition technique introduced by G.~Frederickson and the parallel ear decomposition technique, thus we call it the {\em hammock-on-ears decomposition}. We mention that hammock-on-ears decomposition also draws from techniques in computational geometry and that an embedding of the graph does not need to be provided with the input. We achieve this decomposition in $O(\log n\log\log n)$ time using $O(n+m)$ CREW PRAM processors, for an $n$-vertex, $m$-edge graph or digraph. The hammock-on-ears decomposition implies a general framework for solving graph problems efficiently. Its value is demonstrated by a variety of applications on a significant class of (di)graphs, namely that of {\em sparse (di)graphs}. This class consists of all (di)graphs which have a $\tilde{\gamma}$ between $1$ and $\Theta(n)$, and includes planar graphs and graphs with genus $o(n)$. We improve previous bounds for certain instances of shortest paths and related problems, in this class of graphs. These problems include all pairs shortest paths, all pairs reachability,