Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |

Parallel Decomposition of Generalized

Series-Parallel Graphs

**Chin-Wen Ho, Sun-Yuan Hsieh ^{+} and Gen-Huey Chen^{+}**

National Central University

Chung-Li, Taiwan 320, R.O.C.

National Taiwan University

Taipei, Taiwan 106, R.O.C.

Generalized series-parallel (GSP) graphs belong to the class of decomposable graphs which can be represented by their decomposition trees. Given a decomposition tree of a *GSP* graph, there are many graph-theoretic problems which can be solved efficiently. An efficient parallel algorithm for constructing a decomposition tree of a given GSP graph is presented. It takes *O*(log *n*) time with *C*(*m*, *n*) processors on a CRCW PRAM, where*C*(*m*, *n*) is the number of processors required to find connected components of a graph with *m* edges and *n* vertices in logarithmic time. Based on our algorithmic results, we also derive some properties for *GSP* graphs, which may be of interest in and of themselves.

Keywords: parallel algorithm, generalized series-parallel graph, CRCW PRAM, decomposable graph, decomposition tree

Retrieve PDF document (**199905_06.pdf** : 69,711 bytes)

Received July 17, 1997; accepted May 1, 1998.

Communicated by Wen-Lian Hsu.
^{*}A preliminary version of this paper appeared in the proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'7) Las Vegas, Nevada, pp. 890-896, 1997.

Research supported in part by NSC under Grant 83-0408-E-008-004.