Parallel decomposition of generalized series-parallel graphs

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

研究成果: Article同行評審

5 引文 斯高帕斯(Scopus)

摘要

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.

原文English
頁(從 - 到)407-417
頁數11
期刊Journal of Information Science and Engineering
15
發行號3
出版狀態Published - 1999 五月 1

All Science Journal Classification (ASJC) codes

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

指紋 深入研究「Parallel decomposition of generalized series-parallel graphs」主題。共同形成了獨特的指紋。

引用此