Title

Two Minimum Spanning Forest Algorithms On Fixed-Size Hypercube Computers

Keywords

Graph problems; Hypercube computers; Minimum spanning forest; Parallel algorithms

Abstract

Two parallel algorithms for finding minimum spanning forest (MSF) of a weighted undirected graph on hypercube computers, consisting of a fixed number of processors, are presented. One algorithm is suited for sparse graphs, the other for dense graphs. Our design strategy is based on successive elimination of non-MSF edges. The input graph is partitioned equally among different processors, which then repeatedly eliminate non-MSF edges and merge results to gradually construct the desired MSF of the entire graph. Low communication overhead is achieved by restricting the message-flow to between the neighboring processors in the hypercube topology. The correctness of our approach is due to a theorem which states that with total-ordered edges, if an edge of an arbitrary subgraph does not belong to its MSF, then it does not belong to the MSF of the entire graph. For a graph of n vertices and m edges, our first algorithm finds an MSF in O(m log m)/p) time using p processors for p ≤ (mlog m)/n(1+log(m/n)). The second algorithm, efficient for dense graphs, requires O(n2/p) time for p≤n/log n. © 1990.

Publication Date

1-1-1990

Publication Title

Parallel Computing

Volume

15

Issue

1-3

Number of Pages

179-187

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/0167-8191(90)90041-7

Socpus ID

0025491081 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS