The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Dijkstra, E. W. (1976) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,733
(1973) · North-Holland Mathematical Library · doi:10.1016/s0924-6509(09)x7013-3 · Cited by 2,937
Incidence matrices and interval graphs
Fulkerson, D., & Gross, O. (1965) · Pacific Journal of Mathematics · doi:10.2140/pjm.1965.15.835 · Cited by 1,262
Algorithmic Aspects of Vertex Elimination on Graphs
Rose, D. J., Tarjan, R. E., & Lueker, G. S. (1976) · SIAM Journal on Computing · doi:10.1137/0205021 · Cited by 1,203
Self-citationDirac, G. A. (1961) · Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg · doi:10.1007/bf02992776 · Cited by 927
On the Desirability of Acyclic Database Schemes
Beeri, C., Fagin, R., Maier, D., & Yannakakis, M. (1983) · Journal of the ACM · doi:10.1145/2402.322389 · Cited by 808
Self-citationTriangulated graphs and the elimination process
Rose, D. J. (1970) · Journal of Mathematical Analysis and Applications · doi:10.1016/0022-247x(70)90282-9 · Cited by 500
A simplied universal relation assumption and its properties
Fagin, R., Mendelzon, A. O., & Ullman, J. D. (1982) · ACM Transactions on Database Systems · doi:10.1145/319732.319735 · Cited by 296
Bernstein, P. A., & Goodman, N. (1981) · SIAM Journal on Computing · doi:10.1137/0210059 · Cited by 226
Some Basic Techniques for Solving Sparse Systems of Linear Equations
Gustavson, F. G. (1972) · Springer eBooks · doi:10.1007/978-1-4615-8675-3_4 · Cited by 131
Cited by
(1988) · Cited by 16,582
Lauritzen, S. L., & Spiegelhalter, D. J. (1988) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1988.tb01721.x · Cited by 3,902
Dechter, R., Meiri, I., & Pearl, J. (1991) · Artificial Intelligence · doi:10.1016/0004-3702(91)90006-6 · Cited by 1,799
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · Cited by 1,483
Adaptive Computation and Machine Learning
(2012) · Boosting · doi:10.7551/mitpress/8291.003.0026 · Cited by 1,402
iSAM2: Incremental smoothing and mapping using the Bayes tree
Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J. J., & Dellaert, F. (2012) · The International Journal of Robotics Research · doi:10.1177/0278364911430419 · Cited by 1,362
Bomze, I. M., Budinich, M., Pardalos, P. M., & Pelillo, M. (1999) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4757-3023-4_1 · Cited by 1,148
The NP-completeness column: An ongoing guide
Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 794
Beinlich, I. A., Suermondt, H. J., Chavez, R. M., & Cooper, G. F. (1989) · Lecture Notes in Medical Informatics · doi:10.1007/978-3-642-93437-7_28 · Cited by 724
Bayesian Analysis in Expert Systems
Spiegelhalter, D. J., Dawid, A. P., Lauritzen, S. L., & Cowell, R. G. (1993) · Statistical Science · doi:10.1214/ss/1177010888 · Cited by 684
Lauritzen, S. L., & Wermuth, N. (1989) · The Annals of Statistics · doi:10.1214/aos/1176347003 · Cited by 672
Axioms for Probability and Belief-Function Propagation
Shenoy, P. P., & Shafer, G. (2008) · Studies in Fuzziness and Soft Computing · doi:10.1007/978-3-540-44792-4_20 · Cited by 507
Inference in belief networks: A procedural guide
Huang, C., & Darwiche, A. (1996) · International Journal of Approximate Reasoning · doi:10.1016/s0888-613x(96)00069-2 · Cited by 450
Identifying the Minimal Transversals of a Hypergraph and Related Problems
Eiter, T., & Gottlob, G. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793250299 · Cited by 437
Exploiting Causal Independence in Bayesian Network Inference
Zhang, N. L., & Poole, D. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.305 · Cited by 433
Perspectives on the theory and practice of belief functions
Shafer, G. (1990) · International Journal of Approximate Reasoning · doi:10.1016/0888-613x(90)90012-q · Cited by 429
Pardalos, P. M., & Xue, J. (1994) · Journal of Global Optimization · doi:10.1007/bf01098364 · Cited by 382
An Introduction to Chordal Graphs and Clique Trees
Blair, J. R. S., & Peyton, B. (1993) · The IMA Volumes in Mathematics and its Applications · doi:10.1007/978-1-4613-8369-7_1 · Cited by 377
An Optimal and Distributed Method for Voltage Regulation in Power Distribution Systems
Zhang, B., Lam, A. Y. S., Dominguez-Garcia, A. D., & Tse, D. (2015) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2014.2347281 · Cited by 325
Multiresolution Markov models for signal and image processing
Willsky, A. S. (2002) · Proceedings of the IEEE · doi:10.1109/jproc.2002.800717 · Cited by 305
Probabilistic Reasoning in Expert Systems
Spiegelhalter, D. J. (1989) · American Journal of Mathematical and Management Sciences · doi:10.1080/01966324.1989.10737262 · Cited by 280
A Survey of Relaxations and Approximations of the Power Flow Equations
Molzahn, D. K., & Hiskens, I. A. (2019) · Foundations and Trends® in Electric Energy Systems · doi:10.1561/3100000012 · Cited by 272
Elements of Relational Database Theory
KANELLAKIS, P. C. (1990) · Formal Models and Semantics · doi:10.1016/b978-0-444-88074-1.50022-6 · Cited by 259
Metadata
- Authors
- Tarjan, R. E., & Yannakakis, M.
- Venue
- SIAM Journal on Computing
- Published
- 1984-08
- Volume
- 13
- Issue
- 3
- Pages
- 566-579
- ISSN
- 0097-5397 (ISSN-L)
- 1095-7111
- OpenAlex
- W1991477862
- Cited by
- 1,058
- References
- 11
- FWCI
- 16.69
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.