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

Journal of Inforamtion Science and Engineering, Vol.15 No.3, pp.407-417 (May 1999)
Parallel Decomposition of Generalized
Series-Parallel Graphs*

Chin-Wen Ho, Sun-Yuan Hsieh+ and Gen-Huey Chen+
Department of Computer Science and Information Engineering
National Central University
Chung-Li, Taiwan 320, R.O.C. +Department of Computer Science and Information Engineering
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, whereC(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

Full Text () 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.