Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs
作者： Robert E. Tarjan , Mihalis Yannakakis
DOI: 10.1137/0213035
关键词: Discrete mathematics 、 Combinatorics 、 Chordal graph 、 Graph theory 、 Lexicographic breadth-first search 、 Rose (topology) 、 Mathematics 、 Symmetric matrix 、 Gaussian elimination 、 Algorithm 、 Hypergraph 、 Time complexity
摘要: … Since exactly JR(i)- R’(i)J new vertices are numbered when R (i) is selected, R (i + 1) contains every vertex in R (i)R’(i), and IR’(i+. We can compute the maximal edges of an acyclic …
acm.org
aip.org
sci-hub.se 参考文章(5)
Oded Shmueli, Nathan Goodman, Syntactic Characterizations of Tree Database Schemas. XP2 Workshop on Relational Database Theory. ,(1981)
Fred G. Gustavson, Some Basic Techniques for Solving Sparse Systems of Linear Equations Springer, Boston, MA. pp. 41- 52 ,(1972) , 10.1007/978-1-4615-8675-3_4
Donald J Rose, Triangulated graphs and the elimination process Journal of Mathematical Analysis and Applications. ,vol. 32, pp. 597- 609 ,(1970) , 10.1016/0022-247X(70)90282-9
David Maier, Jeffrey D. Ullman, Connections in acyclic hypergraphs Theoretical Computer Science. ,vol. 32, pp. 185- 199 ,(1984) , 10.1016/0304-3975(84)90030-6
Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes Journal of the ACM. ,vol. 30, pp. 479- 513 ,(1983) , 10.1145/2402.322389