Computing biconnected components on a hypercube

Author

Woo, Jinwoon ; Sahni, Sartaj

Author_Institution

Minnesota Univ., MN, USA

fYear

1990

fDate

30 Sep-2 Oct 1990

Firstpage

277

Lastpage

283

Abstract

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

Keywords

hypercube networks; parallel algorithms; performance evaluation; NCUBE/7 MIMD hypercube computer; Read´s sequential algorithm; Tarjan-Vishkin algorithm; adjacency matrix representation; biconnected component; dense graphs; hypercube; medium grained MIMD; performance; sequential algorithms; Computer science; Concurrent computing; Extraterrestrial measurements; Hypercubes; Parallel algorithms; Parallel programming; Phase change random access memory; Statistics; Time measurement;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1990. Proceedings., Second IEEE Workshop on Future Trends of

Conference_Location

Cairo

Print_ISBN

0-8186-2088-9

Type

conf

DOI

10.1109/FTDCS.1990.138333

Filename

138333