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

Original language | English |
---|---|

Pages (from-to) | 407-417 |

Number of pages | 11 |

Journal | Journal of Information Science and Engineering |

Volume | 15 |

Issue number | 3 |

Publication status | Published - 1999 May 1 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Human-Computer Interaction
- Hardware and Architecture
- Library and Information Sciences
- Computational Theory and Mathematics

### Cite this

*Journal of Information Science and Engineering*,

*15*(3), 407-417.

}

*Journal of Information Science and Engineering*, vol. 15, no. 3, pp. 407-417.

**Parallel decomposition of generalized series-parallel graphs.** / Ho, Chin Wen; Hsieh, Sun-Yuan; Chen, Gen Huey.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Parallel decomposition of generalized series-parallel graphs

AU - Ho, Chin Wen

AU - Hsieh, Sun-Yuan

AU - Chen, Gen Huey

PY - 1999/5/1

Y1 - 1999/5/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=0032687202&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032687202&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0032687202

VL - 15

SP - 407

EP - 417

JO - Journal of Information Science and Engineering

JF - Journal of Information Science and Engineering

SN - 1016-2364

IS - 3

ER -