Algorithm for relatively small planted clique with small edge probability

DOI10.16183/J.CNKI.JSJTU.2017.10.008MaRDI QIDQ3175452zbMATH OpenFDO

Authors Xuangui Huang

Publication date 18 July 2018

Full work available at URL https://doi.org/10.16183/J.CNKI.JSJTU.2017.10.008

zbMATH Keywords

randomized algorithmrandom graphaverage-case complexityplanted cliquesmall edge probability

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Randomized algorithms (68W20) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Finding a planted clique by adaptive probing
• Finding hidden cliques in linear time with high probability
• A new approach to the planted clique problem
• scientific article; zbMATH DE number 1303602
• scientific article; zbMATH DE number 1380608

Cited in

(2)

• A new approach to the planted clique problem
• Parallel tempering for the planted clique problem

This page was built for publication: Algorithm for relatively small planted clique with small edge probability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3175452)