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

Tarjan, Robert E.; Yannakakis, Mihalis

SIAM J. Comput. 13, 566-579 (1984).

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.

MSC:

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

Keywords:

graph algorithm; acyclic data base scheme; sparse Gaussian elimination; graph search; Chordal graphs; acyclic hypergraphs

Citations:

Zbl 0353.65019