Two minimum spanning forest algorithms on fixed-size hypercube computers |
| |
Authors: | Sajal K Das Narsingh Deo Sushil Prasad |
| |
Affiliation: | * Department of Computer Science, University of North Texas, Denton, TX 76203-3886, USA ? Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA |
| |
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. |
| |
Keywords: | Graph problems Hypercube computers Minimum spanning forest Parallel algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|