On approximating the number of k-cliques in sublinear time

DOI10.1145/3188745.3188810zbMath1428.68212arXiv1707.04858OpenAlexW2963613355MaRDI QIDQ5230333

C. Seshadhri, Dana Ron, Talya Eden

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.04858

zbMATH Keywords

approximation algorithmssublinear algorithmscounting cliques

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (4)

On triangle estimation using tripartite independent set queries ⋮ Unnamed Item ⋮ A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling ⋮ Quantum Chebyshev's Inequality and Applications

This page was built for publication: On approximating the number of k-cliques in sublinear time