Parallel Algorithms for Bridge- and Bi-Connectivity on Minimum Area Meshes
Susanne E. Hambrusch · Purdue e-Pubs (Purdue University System) · 1985
We present parallel algorithms for finding tbe bridgeand bi~onDected components of an undirected graph G =(V .E) with n vertices and t1 edges on 2-dimensiooal mesh of size n1/lxnJ/2. In conventional parallel models any bridge. and bi-connectivity algorithm requires at least n processing elements, and tbus our algorithms run on minimum area networks. OUf algorithms find tbe bridge-connected components in 0(n /2) time for both input in the form of an adjacency matrix and in the form of edges. For bi-connectivity we show how achieve 0 (n 3/2) time when the input is adjacency matrix form, and 0 (e +n312) time when the input is in the form of edges.