PARALLEL BLOCK-FINDING USING DISTANCE MATRICES

Author:

Abstract
We present a fast parallel algorithm for finding the blocks or biconnected components of an undirected graph G = (V,E ) having n vertices and m edges. Our techniques arc based on partitioning the vertex set V into adjacency-level sets using information contained in the distance matrix D of the graph. Let t D and p D be the time and number of processors, respectively, for the computation of the distance matrix of a graph G on a CRCW-PRAM computational model. We show that the location of all cut vertices and bridges of a graph can be done in time O(logδ + t D) by using O(n m/t d) processors, where δ is the maximum degree of a vertex in G. Based on these results, we define a digraph G d and we prove certain properties on its distance matrix leading to a parallel block-finding algorithm running in time O(logδ + t D) with O(n m/t D) processors on the same computational model. We also show that other connectivity-related problems can be efficiently solved using distance matrices.

This publication has 13 references indexed in Scilit: