Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
SIAM Journal on Computing1984Vol. 13(3), pp. 566–579
Citations Over TimeTop 1% of 1984 papers
Abstract
Chordal graphs arise naturally in the study of Gaussian elimination on sparse symmetric matrices; acyclic hypergraphs arise in the study of relational data bases. Rose, Tarjan and Lueker [SIAM J. Comput., 5 (1976), pp. 266–283] 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 acyclic relational data bases.
Related Papers
- → Hypergraph Modeling(2023)1 cited
- → Decompositions of 3-uniform hypergraph K_v^{(3)} into hypergraph K_4^{(3)}+e(2010)
- → On the Random Greedy $F$-Free Hypergraph Process(2015)
- → Non-uniform Hypergraphs(2020)
- On the random greedy F-free hypergraph process(2015)