The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Hirotoshi HONMA, Shigeru MASUYAMA, "An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E91-A, no. 9, pp. 2296-2300, September 2008, doi: 10.1093/ietfec/e91-a.9.2296.

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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e91-a.9.2296/_p

Copy

@ARTICLE{e91-a_9_2296,

author={Hirotoshi HONMA, Shigeru MASUYAMA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Optimal Parallel Algorithm for Constructing a Spanning Forest on Trapezoid Graphs},

year={2008},

volume={E91-A},

number={9},

pages={2296-2300},

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.},

keywords={},

doi={10.1093/ietfec/e91-a.9.2296},

ISSN={1745-1337},

month={September},}

Copy

TY - JOUR

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

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2296

EP - 2300

AU - Hirotoshi HONMA

AU - Shigeru MASUYAMA

PY - 2008

DO - 10.1093/ietfec/e91-a.9.2296

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E91-A

IS - 9

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - September 2008

AB - 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.

ER -