PARALLEL BLOCK-FINDING USING DISTANCE MATRICES
Author:
- 1 January 1996
- journal article
- research article
- Published by Taylor & Francis in Parallel Algorithms and Applications
- Vol. 9 (1-2) , 1-13
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.Keywords
This publication has 13 references indexed in Scilit:
- FAST PARALLEL ALGORITHMS FOR FINDING CUTPOINTS AND BRIDGES OF UNDIRECTED GRAPHSParallel Algorithms and Applications, 1994
- Optimal parallel algorithms for finding cut vertices and bridges of interval graphsInformation Processing Letters, 1992
- Optimal bounds for decision problems on the CRCW PRAMJournal of the ACM, 1989
- A general program scheme for finding bridgesInformation Processing Letters, 1983
- Implementation of simultaneous memory address access in models that forbid itJournal of Algorithms, 1983
- Parallel computation and conflicts in memory accessInformation Processing Letters, 1982
- An O(logn) parallel connectivity algorithmJournal of Algorithms, 1982
- Fast, Efficient Parallel Algorithms for Some Graph ProblemsSIAM Journal on Computing, 1981
- Parallel Matrix and Graph AlgorithmsSIAM Journal on Computing, 1981
- Status and ContrastatusSociometry, 1959