Some spin glass ideas applied to the clique problem
From MaRDI portal
(Redirected from Publication:885046)
Abstract: In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.
Recommendations
Cites work
- scientific article; zbMATH DE number 956839 (Why is no real title available?)
- Large Cliques Elude the Metropolis Process
- Maximum sizes of graphs with given domination parameters
- Mining relevant information on the Web: a clique-based approach
- Reactive local search for the maximum clique problem
- The cavity method at zero temperature
- Using constraint programming to solve the maximum clique problem
Cited in
(9)- Gaussian mean field lattice gas
- Sampling from a Gibbs measure with pair interaction by means of PCA
- Equilibrium and non-equilibrium Ising models by means of PCA
- Metastable states, quasi-stationary distributions and soft measures
- Parallel tempering for the planted clique problem
- Probabilistic cellular automata for low-temperature 2-d Ising model
- Phase transitions for the cavity approach to the clique problem on random graphs
- Sampling the Fermi statistics and other conditional product measures
- Finding one community in a sparse graph
This page was built for publication: Some spin glass ideas applied to the clique problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q885046)
