Blair, Jean R. S.; Peyton, Barry W. On finding minimum-diameter clique trees. (English) Zbl 0819.68085 Nord. J. Comput. 1, No. 2, 173-201 (1994). Summary: A clique-tree representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. Since some chordal graphs have many distinct clique- tree representations, it is interesting to consider which one is most desirable under various circumstances. A clique tree of minimum diameter (or height) is sometimes a natural candidate when choosing clique trees to be processed in a parallel-computing environment. This paper introduces a linear-time algorithm for computing a minimum-diameter clique tree. Cited in 9 Documents MSC: 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity Keywords:clique-tree representation; chordal graph PDFBibTeX XMLCite \textit{J. R. S. Blair} and \textit{B. W. Peyton}, Nord. J. Comput. 1, No. 2, 173--201 (1994; Zbl 0819.68085)