The search functionality is under construction.
The search functionality is under construction.

An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs

Hirotoshi HONMA, Shigeru MASUYAMA

  • Full Text Views

    0

  • Cite this

Summary :

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E91-A No.9 pp.2296-2300
Publication Date
2008/09/01
Publicized
Online ISSN
1745-1337
DOI
10.1093/ietfec/e91-a.9.2296
Type of Manuscript
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category

Authors

Keyword