Parallel decomposition of generalized series-parallel graphs

作     者：Ho, CW Hsieh, SY Chen, GH Chin-Wen Ho;Sun-Yuan Hsieh;Gen-Huey Chen

作者机构：Natl Cent Univ Dept Comp Sci & Informat Engn Chungli 320 Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 106 Taiwan 

出 版 物：《JOURNAL OF INFORMATION SCIENCE AND ENGINEERING》 (J. Inf. Sci. Eng.)

年 卷 期：1999年第15卷第3期

页      面：407-417页

核心收录：

主　　题：parallel algorithm generalized series-parallel graph CRCW PRAM decomposable graph decomposition tree 

摘      要：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.