Parallel decomposition of generalized series-parallel graphs

Chin Wen Ho, Sun-Yuan Hsieh, Gen Huey Chen

Research output: Contribution to journalArticle

4 Citations (Scopus)

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 languageEnglish
Pages (from-to)407-417
Number of pages11
JournalJournal of Information Science and Engineering
Volume15
Issue number3
Publication statusPublished - 1999 May 1

Fingerprint

Decomposition
Parallel algorithms
time

All Science Journal Classification (ASJC) codes

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

Cite this

@article{ed733863e97243e9bd244048b1ae7874,
title = "Parallel decomposition of generalized series-parallel graphs",
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.",
author = "Ho, {Chin Wen} and Sun-Yuan Hsieh and Chen, {Gen Huey}",
year = "1999",
month = "5",
day = "1",
language = "English",
volume = "15",
pages = "407--417",
journal = "Journal of Information Science and Engineering",
issn = "1016-2364",
publisher = "Institute of Information Science",
number = "3",

}

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

In: Journal of Information Science and Engineering, Vol. 15, No. 3, 01.05.1999, p. 407-417.

Research output: Contribution to journalArticle

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 -