×

On finding minimum-diameter clique trees. (English) Zbl 0819.68085

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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite