AbstractA 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.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory
Additional Key Words and Phrases: chordal graphs, clique trees, acyclic hypergraphs, parallel computing
Selected references
- Catriel Beeri, Ronald Fagin, David Maier, and Mihalis Yannakakis. On the desirability of acyclic database schemes. Journal of the ACM, 30(3):479-513, July 1983.
- Philip A. Bernstein and Nathan Goodman. Power of natural semijoins. SIAM Journal on Computing, 10(4):751-771, November 1981.
- Ronald Fagin. Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM, 30(3):514-550, July 1983.
- F\u{a}nic\u{a} Gavril. Generating the maximum spanning trees of a weighted graph. Journal of Algorithms, 8(4):592-597, December 1987.
- Robert E. Tarjan and Mihalis Yannakakis. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM Journal on Computing, 13(3):566-579, August 1984.