Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. (English) Zbl 0545.68062

Summary: Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. D. J. Rose, R. E. Tarjan and G. S. Lueker [ibid. 5, 266-283 (1976; Zbl 0353.65019)] have given a linear- time algorithm to test whether a graph is chordal, which Yannakakis has modified to test whether a hypergraph is acyclic. Here we develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which we call maximum cardinality search. A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acylic relational data bases.


68R10 Graph theory (including graph drawing) in computer science
65F05 Direct numerical methods for linear systems and matrix inversion
68P20 Information storage and retrieval of data
65F50 Computational methods for sparse matrices
05C65 Hypergraphs


Zbl 0353.65019
Full Text: DOI