Parallel tempering for the planted clique problem

DOI10.1088/1742-5468/aace2czbMath1456.68233arXiv1802.05903OpenAlexW2787305781MaRDI QIDQ3303299

Maria Chiara Angelini

Publication date: 11 August 2020

Published in: Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Random graphs (graph-theoretic aspects) (05C80) 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)

Related Items

Mismatching as a tool to enhance algorithmic performances of Monte Carlo methods for the planted clique model ⋮ Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning

Cites Work

• Unnamed Item
• Unnamed Item
• Finding one community in a sparse graph
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Computational barriers in minimax submatrix detection
• Computational and statistical boundaries for submatrix localization in a large noisy matrix
• Community detection in dense random networks
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• Cliques in random graphs
• Statistical mechanics of the vertex-cover problem