Nordic Journal of Computing Bibliography

J. R. S. Blair and B. W. Peyton. On finding minimum-diameter clique trees. Nordic Journal of Computing, 1(2):173-201, Summer 1994.
Abstract

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.

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


Shortcuts:

  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database