查詢結果分析
相關文獻
頁籤選單縮合
題 名 | Parallel Decomposition of Generalized Series-Parallel Graphs |
---|---|
作 者 | 何錦文; 謝孫源; 陳健輝; | 書刊名 | Journal of Information Science and Engineering |
卷 期 | 15:3 1999.05[民88.05] |
頁 次 | 頁407-417 |
專 輯 | Special Section on Algorithms |
分類號 | 319.76 |
關鍵詞 | Parallel algorithm; Generalized series-parallel graph; CRCW PRAM; Decomposable graph; Decomposition tree; |
語 文 | 英文(English) |
英文摘要 | 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. |
本系統中英文摘要資訊取自各篇刊載內容。