Efficient k-Clique Listing: An Edge-Oriented Branching Strategy

Summary: Proposes edge-oriented branching (EBBkC) for k-clique listing, formulating sub-branches by expanding edges instead of vertices. Yields O(m*delta + k*m*(tau/2)^(k-2)) time (tau<delta), outperforming VBBkC (O(k*m*(delta/2)^(k-2))) for k>3; with dense-graph early-termination techniques, it excels in 19 real graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h3bd19b8262323705
Venue: SIGMOD
Year: 2024
Pagerank: 7.1643588e-05
Overall Rank: 3,610 | 75.73%
DOI: 10.1145/3639262

Incoming Non-self Citations Over Time

Authors

1. Kaixin Wang (Nanyang Technological University)
2. Kaiqiang Yu (Nanyang Technological University)
3. Cheng Long (Nanyang Technological University)

BibTeX Citation

@inproceedings{wang_sigmod24,
        title = {{Efficient k-Clique Listing: An Edge-Oriented Branching Strategy}},
        author = {Wang, Kaixin and Yu, Kaiqiang and Long, Cheng},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639262},
        url = {https://dl.acm.org/doi/10.1145/3639262},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,775	Efficient k-Clique Count Estimation with Accuracy Guarantee	2024	VLDB	5.4548071e-05
8,884	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD	5.2559789e-05
9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.1435978e-05
10,056	Finding Logic Bugs in Graph-processing Systems via Graph-cutting	2025	SIGMOD	5.0875952e-05
10,481	Maximal Biclique Enumeration with Improved Worst-Case Time Complexity Guarantee: A Partition-Oriented Strategy	2026	SIGMOD	4.9793485e-05
10,537	The Power of Core Clique Removal for Exact Clique Enumeration	2026	SIGMOD	4.9793485e-05
10,567	Estimating Biclique Counts with Accuracy Guarantees	2026	SIGMOD	4.9793485e-05
10,612	A Unified Framework for Dense Subgraph Maintenance over Dynamic Bipartite Graphs	2026	SIGMOD	4.9793485e-05
10,789	CREST: Approximate k-Clique Counting in Real-World Networks via Refinement of Star-Based Sample Space	2026	VLDB	4.9793485e-05
11,321	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.9793485e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
988	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012660447
1,507	Finding the Maximum Clique in Massive Graphs	2017	VLDB	0.00010450256
2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.1416822e-05
3,495	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2562279e-05
5,781	Effective and Efficient Dynamic Graph Coloring	2018	VLDB	5.9972461e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,526	Maximal Defective Clique Enumeration	2023	SIGMOD
2	1,616	Efficient Enumeration of Maximal k-Plexes	2015	SIGMOD
3	9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD
4	5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
5	3,189	Efficient Maximum k-Plex Computation over Large Sparse Graphs	2023	VLDB
6	11,518	Efficient Maximal Biplex Enumerations with Improved Worst-Case Time Guarantee	2024	SIGMOD
7	5,552	Theoretically and Practically Efficient Maximum Defective Clique Search	2024	SIGMOD
8	8,884	Efficient Defective Clique Enumeration and Search with Worst-Case Optimal Search Space	2026	SIGMOD
9	10,797	Revisiting the Maximum Defective Clique Problem: Faster Branching and a Tighter Upper Bound	2026	VLDB
10	3,860	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD