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: 1720
Venue: PODS
Year: 2017
Pagerank: 5.2876688e-05
Overall Rank: 9,337 | 35.95%
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,461	HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings	2019	PODS	6.2090515e-05
6,929	Mining Approximate Acyclic Schemes from Relations	2020	SIGMOD	5.7369354e-05
7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS	5.5181056e-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
382	Conjunctive-Query Containment and Constraint Satisfaction	1998	PODS	0.00019546431
490	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.000175757
673	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00015095061
3,841	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	7.0808098e-05
6,373	Full Disjunctions: Polynomial-Delay Iterators in Action	2006	VLDB	5.8946564e-05
8,013	Optimizing and Parallelizing Ranked Enumeration	2011	VLDB	5.5073426e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,375	Efficiently Counting Triangles in Large Temporal Graphs	2025	SIGMOD
2	5,028	Minimum Spanning Trees in Temporal Graphs	2015	SIGMOD
3	458	Counting Triangles in Data Streams	2006	PODS
4	8,623	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
5	5,540	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
6	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
7	2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS
8	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
9	594	Massive Graph Triangulation	2013	SIGMOD
10	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS