Parallel decomposition of generalized series-parallel graphs
Resource
Journal of Information Science and Engineering,15(3),407-417.
Journal
Journal of Information Science and Engineering
Pages
407-417
Date Issued
1999-03
Date
1999-03
Author(s)
Ho, C. W.
Hsieh, S. Y.
Chen, G. H.
Abstract
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.
Type
journal article