Computing biconnected components on a hypercube
J. Woo, Sartaj K. Sahni · 2002
Two biconnected component (i.e., block) algorithms suitable for medium grained MIMD (multiple-instruction/multiple-data) hypercubes are developed. Both algorithms are for dense graphs and use the adjacency matrix representation of a graph. The two hypercube algorithms are adaptations of existing sequential algorithms. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms are experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 have been observed on dense graphs.>