1.6k citations · 6.9k across the 61 of their papers we have counts for
5 papers · 1 filter
Constraint Satisfaction by Survey Propagation
A. Braunstein, M. Mezard, M. Weigt +1
Survey Propagation is an algorithm designed for solving typical instances of random constraint satisfiability problems. It has been successfully tested on random 3-SAT and random $…
Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
M. Weigt, A. K. Hartmann
We introduce a hard-core lattice-gas model on generalized Bethe lattices and investigate analytically and numerically its compaction behavior. If compactified slowly, the system un…
Computational complexity arising from degree correlations in networks
Alexei Vazquez, Martin Weigt
We apply a Bethe-Peierls approach to statistical-mechanics models defined on random networks of arbitrary degree distribution and arbitrary correlations between the degrees of neig…
Towards finite-dimensional gelation
Kurt Broderix, Martin Weigt, Annette Zippelius
We consider the gelation of particles which are permanently connected by random crosslinks, drawn from an ensemble of finite-dimensional continuum percolation. To average over the…
Dynamics of heuristic optimization algorithms on random graphs
Martin Weigt
In this paper, the dynamics of heuristic algorithms for constructing small vertex covers (or independent sets) of finite-connectivity random graphs is analysed. In every algorithmi…