An introduction to chordal graphs and clique trees. (English) Zbl 0803.68081

George, Alan (ed.) et al., Graph theory and sparse matrix computation. Proceedings of a workshop that was an integral part of the 1991-92 IMA program on “Applied linear algebra”, Minneapolis, MN (USA). New York: Springer-Verlag. IMA Vol. Math. Appl. 56, 1-29 (1993).
Summary: Clique trees and chordal graphs have carved out a niche for themselves in recent work on sparse matrix algorithms, due primarily to research questions associated with advanced computer architectures. This paper is a unified and elementary introduction to the standard characterizations of chordal graphs and clique trees. The pace is leisurely, as detailed proofs of all results are included. We also briefly discuss applications of chordal graphs and clique ttrees in sparse matrix computations.
For the entire collection see [Zbl 0785.00030].


68R10 Graph theory (including graph drawing) in computer science
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
65F50 Computational methods for sparse matrices
68Q25 Analysis of algorithms and problem complexity
15A23 Factorization of matrices