Title
Hammock-On-Ears Decomposition: A Technique For The Efficient Parallel Solution Of Shortest Paths And Other Problems
Abbreviated Journal Title
Theor. Comput. Sci.
Keywords
Planar Graphs; Algorithm; Genus; Computer Science, Theory & Methods
Abstract
We show how to decompose efficiently in parallel any graph into a number, < (gamma)over tilde >, of outerplanar subgraphs (called hammocks) satisfying certain separator properties. Our work combines and extends the sequential hammock decomposition technique introduced by Frederickson and the parallel ear decomposition technique, thus we call it the 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 graphs, namely that of sparse (di)graphs. This class consists of all (di)graphs which have a < (gamma)over tilde > between 1 and O(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, and detection of a negative cycle.
Journal Title
Theoretical Computer Science
Volume
168
Issue/Number
1
Publication Date
1-1-1996
Document Type
Article
Language
English
First Page
121
Last Page
154
WOS Identifier
ISSN
0304-3975
Recommended Citation
"Hammock-On-Ears Decomposition: A Technique For The Efficient Parallel Solution Of Shortest Paths And Other Problems" (1996). Faculty Bibliography 1990s. 793.
https://stars.library.ucf.edu/facultybib1990/793
Comments
Authors: contact us about adding a copy of your work at STARS@ucf.edu