Paper Info
Title
An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs
Abstract
Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. An optimal parallel algorithm for finding a spanning tree on the trapezoid graph is given by Bera et al., it takes O(log n) time with O(n/log n) processors on the EREW (Exclusive-Read Exclusive-Write) PRAM. Bera et al.'s algorithm is very simple and elegant. Moreover, it can correctly construct a spanning tree when the graph is connected. However, their algorithm can not accept a disconnected graph as an input. Applying their algorithm to a disconnected graph, Concurrent-Write occurs once for each connected component, thus this can not be achieved on EREW PRAM. In this paper we present an O(log n) time parallel algorithm with O(n/log n) processors for constructing a spanning forest on trapezoid graph G on EREW PRAM even if G is a disconnected graph.
Year
DOI
Venue
2008
10.1093/ietfec/e91-a.9.2296
IEICE Transactions
Keywords
Field
DocType
optimal parallel algorithm,trapezoid graph,trapezoid graphs,n vertex,electrical power demand problem,erew pram,simple graph,connected component,time parallel algorithm,spanning forest,disconnected graph,log n,electric power,spanning tree,computer network,parallel algorithm,parallel algorithms
Pseudoforest,Discrete mathematics,Combinatorics,Tree (graph theory),Graph factorization,Theoretical computer science,Connected dominating set,Spanning tree,Kruskal's algorithm,Reverse-delete algorithm,Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
E91-A
9
0916-8508
Citations 
PageRank 
References 
1
0.36
10
Authors
2
Name
Order
Citations
PageRank
Hirotoshi Honma1309.77
Shigeru Masuyama210728.06