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).

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