Counting clique trees and computing perfect elimination schemes in parallel

Chin Wen Ho, R. C.T. Lee

研究成果: 雜誌貢獻期刊論文同行評審

57 引文 斯高帕斯(Scopus)

摘要

In a previous result, the authors showed that a clique tree of a chordal graph can be constructed in O(log n) parallel computing time with O(n3) processors on CRCW PRAM, where n is the number of nodes of the graph. In this paper, it will be shown that this result can be extended in two ways. First, we show that from the parallel clique tree constructing algorithm, we can derive an exact formula of counting clique trees of a labeled connected chordal graph. Next, we show that a perfect elimination scheme of a chordal graph can be computed in O(log n) time with O(n2) processors on CREW PRAM once a clique tree of the graph is given. This implies that a perfect elimination scheme of a chordal graph can be computed in O(log n) time with O(n3) processors on CRCW PRAM.

原文???core.languages.en_GB???
頁(從 - 到)61-68
頁數8
期刊Information Processing Letters
31
發行號2
DOIs
出版狀態已出版 - 26 4月 1989

指紋

深入研究「Counting clique trees and computing perfect elimination schemes in parallel」主題。共同形成了獨特的指紋。

引用此