Counting clique trees and computing perfect elimination schemes in parallel

Chin Wen Ho, R. C.T. Lee

Research output: Contribution to journalArticlepeer-review

57 Scopus citations

Abstract

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.

Original languageEnglish
Pages (from-to)61-68
Number of pages8
JournalInformation Processing Letters
Volume31
Issue number2
DOIs
StatePublished - 26 Apr 1989

Keywords

  • chordal graphs
  • clique trees
  • CRCW PRAM
  • CREW PRAM
  • Parallel processing

Fingerprint

Dive into the research topics of 'Counting clique trees and computing perfect elimination schemes in parallel'. Together they form a unique fingerprint.

Cite this