max planck institut
informatik

# 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:

MPI-I-94-131.pdf135 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
BibTeX