HAMMOCK-ON-EARS DECOMPOSITION - A TECHNIQUE FOR THE EFFICIENT PARALLEL SOLUTION OF SHORTEST PATHS AND OTHER PROBLEMS

We show how to decompose efficiently in parallel any graph into a numb er, <(gamma)over tilde>, of outerplanar subgraphs (called hammocks) sa tisfying certain separator properties. Our work combines and extends t he sequential hammock decomposition technique introduced by Fredericks on and the parallel ear decomposition technique, thus we call it the h ammock-on-ears decomposition. We mention that hammock-on-ears decompos ition also draws from techniques in computational geometry and that an embedding of the graph does not need to be provided with the input. W e 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 h ammock-on-ears decomposition implies a general framework for solving g raph problems efficiently. Its value is demonstrated by a variety of a pplications on a significant class of graphs, namely that of sparse (d i)graphs. This class consists of all (di)graphs which have a <(gamma)o ver tilde> between 1 and O(n), and includes planar graphs and graphs w ith genus o(n). We improve previous bounds for certain instances of sh ortest paths and related problems, in this class of graphs. These prob lems include all pairs shortest paths, all pairs reachability, and det ection of a negative cycle.