Efficiently Enumerating Minimal Triangulations

Summary: Enumerates all minimal triangulations of a graph in incremental polynomial time, hence all proper tree decompositions (no bag removable or splittable). Framework wraps any single-result triangulation/decomposition as an anytime enumerator and yields many higher-quality decompositions in practice. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1774958cc8f61efd
Venue: PODS
Year: 2017
Pagerank: 5.1690578e-05
Overall Rank: 9,516 | 36.03%
DOI: 10.1145/3034786.3056109

Incoming Non-self Citations Over Time

Authors

1. Nofar Carmeli (Technion)
2. Batya Kenig (Technion)
3. Benny Kimelfeld (Technion)

BibTeX Citation

@inproceedings{carmeli_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{Efficiently Enumerating Minimal Triangulations}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3056109},
        doi = {10.1145/3034786.3056109},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Carmeli, Nofar and Kenig, Batya and Kimelfeld, Benny},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,601	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.0706976e-05
6,589	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7427998e-05
8,091	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.3942942e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
390	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019248147
466	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00017773029
684	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00014798237
3,908	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	6.9320489e-05
6,499	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.7650247e-05
8,154	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.3889102e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,907	On Asymptotic Cost of Triangle Listing in Random Graphs	2017	PODS
2	5,150	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD
3	462	Counting Triangles in Data Streams	2006	PODS
4	8,772	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
5	5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
6	5,232	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
7	2,215	The Input/Output Complexity of Triangle Enumeration	2014	PODS
8	1,121	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
9	600	Massive Graph Triangulation	2013	SIGMOD
10	8,091	Ranked Enumeration of Minimal Triangulations	2019	PODS