Large Cliques Elude the Metropolis Process
From MaRDI portal
Publication:4019371
DOI10.1002/rsa.3240030402zbMath0754.60018WikidataQ56210421 ScholiaQ56210421MaRDI QIDQ4019371
Publication date: 16 January 1993
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.3240030402
Related Items
Finding Hidden Cliques in Linear Time with High Probability, Coloring random graphs, Optimal detection of sparse principal components in high dimension, Comment on ``Hypothesis testing by convex optimization, The complexity of explicit constructions, Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs, Some spin glass ideas applied to the clique problem, Finding one community in a sparse graph, Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, What do we know about the Metropolis algorithm?, The Metropolis algorithm for graph bisection, A slowly mixing Markov chain with implications for Gibbs sampling, Speeding up branch and bound algorithms for solving the maximum clique problem, Computational barriers in minimax submatrix detection, Improvements to MCS algorithm for the maximum clique problem, Finding large cliques in sparse semi-random graphs by simple randomized search heuristics, A new genetic algorithm, Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements, The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture, On independent sets in random graphs, Random Instances of Problems in NP – Algorithms and Statistical Physics