1984/08/01 by Robert E. Tarjan, Mihalis Yannakakis · 1,061 citations
Computer Science · Mathematics · #Data Management and Algorithms #Graph Theory and Algorithms #Bayesian Modeling and Causal Inference #Hypergraph #Chordal graph #Directed acyclic graph #Combinatorics #Cardinality (data modeling) #Mathematics #Time complexity #Simple (philosophy) #Discrete mathematics #Gaussian elimination #Algorithm #Gaussian #Graph #Computer science
paper · doi:10.1137/0213035
published in SIAM Journal on Computing 13(3), 566-579 (Society for Industrial and Applied Mathematics)
openalex publication_date 1984/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/11
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.