Finding cliques using few probes

DOI10.1002/rsa.20896zbMath1442.05207arXiv1809.06950OpenAlexW2982133472WikidataQ126976983 ScholiaQ126976983MaRDI QIDQ5113935

David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali

Publication date: 19 June 2020

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

random graphscliquesadaptive query model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Finding a planted clique by adaptive probing ⋮ On the subgraph query problem

This page was built for publication: Finding cliques using few probes