Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-I-94-131

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

Kavvadias, G. and Pantziou, Grammati E. and Spirakis, P. G. and Zaroliagis, Christos D.

MPI-I-94-131. July 1994, 38 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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,
Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-94-131.pdfMPI-I-94-131.pdfMPI-I-94-131.ps.Z135 KBytes; 286 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1994-131
Hide details for BibTeXBibTeX
@TECHREPORT{KavvadiasPantziouSpirakisZaroliagis94,
  AUTHOR = {Kavvadias, G. and Pantziou, Grammati E. and Spirakis, P. G. and Zaroliagis, Christos D.},
  TITLE = {Hammock-on-ears decomposition: a technique for the efficient parallel solution of shortest paths and other problems},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-94-131},
  MONTH = {July},
  YEAR = {1994},
  ISSN = {0946-011X},
}