MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1

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.

July 1994, 38 pages.

.
Status: available - back from printing

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,

  • MPI-I-94-131.pdfMPI-I-94-131.pdfMPI-I-94-131.ps.Z
  • Attachement: MPI-I-94-131.ps.Z (135 KBytes); MPI-I-94-131.pdf (286 KBytes)

URL to this document: https://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},
}