On Asymptotic Cost of Triangle Listing in Random Graphs

Summary: Introduce a Glivenko–Cantelli–based stochastic framework to model in-memory triangle listing costs in random graph families; derive asymptotically exact CPU limits (n→∞) for all vertex/edge iterators under arbitrary acyclic orientations as closed-form functions of the degree distribution. Enables provable selection of optimal orientations and direct comparison of algorithm classes, identifying the best technique within each class. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1707
Venue: PODS
Year: 2017
Pagerank: 5.3766157e-05
Overall Rank: 8,744 | 40.01%
DOI: 10.1145/3034786.3034790

Incoming Non-self Citations Over Time

Authors

1. Di Xiao (Texas A&M University)
2. Yi Cui (Texas A&M University)
3. Daren B. H. Cline (Texas A&M University)
4. Dmitri Loguinov (Texas A&M University)

BibTeX Citation

@inproceedings{xiao_pods17,
        address = {New York, NY, USA},
        series = {{PODS} '17},
        title = {{On Asymptotic Cost of Triangle Listing in Random Graphs}},
        url = {https://dl.acm.org/doi/10.1145/3034786.3034790},
        doi = {10.1145/3034786.3034790},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Xiao, Di and Cui, Yi and Cline, Daren B. H. and Loguinov, Dmitri},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,530	The Gibbs–Rand Model	2022	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
262	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00023084332
594	Massive Graph Triangulation	2013	SIGMOD	0.00015979077
3,393	OPT: A New Framework for Overlapped and Parallel Triangulation in Large-scale Graphs	2014	SIGMOD	7.45141e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,923	Ranked Enumeration of Minimal Triangulations	2019	PODS
2	8,928	How the Degeneracy Helps for Triangle Counting in Graph Streams	2020	PODS
3	9,337	Efficiently Enumerating Minimal Triangulations	2017	PODS
4	6,363	The Complexity of Counting Cycles in the Adjacency List Streaming Model	2019	PODS
5	1,103	Counting and Sampling Triangles from a Graph Stream	2013	VLDB
6	594	Massive Graph Triangulation	2013	SIGMOD
7	6,873	Triangle and Four Cycle Counting in the Data Stream Model	2020	PODS
8	5,110	Better Algorithms for Counting Triangles in Data Streams	2016	PODS
9	2,183	The Input/Output Complexity of Triangle Enumeration	2014	PODS
10	458	Counting Triangles in Data Streams	2006	PODS