Parallel graph contraction

Publisher Website
Google Scholar
Abstract
This paper shows how n-node, e-edge graphs can be contracted in a mannel ~ similar to the parallel tree contraction algorithm due ~o Miller and Reif. We give an O((n + e)/lgn)-processor deterministic algorithm that contracts a graph in O(lg 2 n) time in the EREW PRAM model. We also give art O(n/lg n)-processor randomized algorithm that with high probability can contract a bounded-degree graph in O(lg n+lg 2 77) time, where 77 is the maximum genus of any connected component of the graph. (The algorithm can be made to run in deterministic O(lg n lg* n + lg ~ 77) time using known techniques.) This algorithm does not require a priori knowledge of the genus of the graph to be contracted. The contraction algorithm for boundeddegree graphs can be used directly to solve the problem of region labeling in vision systems, i.e., determining the connected components of bounded-degree planar graphs in O(lgn) time, thus improving the best previous bound of O(lg 2 n).

This publication has 13 references indexed in Scilit: