Title

Parallel Graph Algorithms For Hypercube Computers

Keywords

Bipartite; bridges; connected components; fundamental cycles; graph problems; hypercube computers; optimal parallel algorithms; spanning forest

Abstract

This paper presents several parallel algorithms on unweighted graphs for hypercube computers. The algorithms are for checking bipartiteness and for finding a spanning forest, the connected components, a fundamental cycle set, and the bridges of a graph. The algorithm for finding spanning forest is based on a strategy of successive elimination of non-forest edges. The input graph is partitioned equally among processors, which repeatedly eliminate non-forest edges and merge their results to finally construct the desired forest of the entire graph. In all the algorithms, low communication overhead is achieved by restricting the message-flow to only between the neighboring processors. The spanning-forest algorithm is used as a subroutine to design the remaining algortihms. Except for the bridge-finding algorithm, all others achieve optimal speedups for dense as well as sparse graphs, and each algorithm is optimally scalable up to a large number of processors depending upon the density of the input graph. For a graph of n vertices and m edges, the time complexity of the spanning-forest algorithm, using p processors, is O(m/p + n log p), which corresponds to an optimal speedup for p ≤(m/n)/(1+log(m/n)). © 1990.

Publication Date

1-1-1990

Publication Title

Parallel Computing

Volume

13

Issue

2

Number of Pages

143-158

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0167-8191(90)90143-W

Socpus ID

0025387580 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0025387580

This document is currently not available here.

Share

COinS