Geodesic
A note on the Glauber dynamics for sampling independent sets
The electronic journal of combinatorics, Tome 8 (2001) no. 1

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
This note considers the problem of sampling from the set of weighted independent sets of a graph with maximum degree $\Delta$. For a positive fugacity $\lambda$, the weight of an independent set $\sigma$ is $\lambda^{|\sigma|}$. Luby and Vigoda proved that the Glauber dynamics, which only changes the configuration at a randomly chosen vertex in each step, has mixing time $O(n\log{n})$ when $\lambda < {{2}\over {\Delta-2}}$ for triangle-free graphs. We extend their approach to general graphs.
DOI : 10.37236/1552
Classification : 68W20, 60J10
Mots-clés : sampling, Glauber dynamics 
Eric Vigoda. A note on the Glauber dynamics for sampling independent sets. The electronic journal of combinatorics, Tome 8 (2001) no. 1. doi: 10.37236/1552
@article{10_37236_1552,
     author = {Eric Vigoda},
     title = {A note on the {Glauber} dynamics for sampling independent sets},
     journal = {The electronic journal of combinatorics},
     year = {2001},
     volume = {8},
     number = {1},
     doi = {10.37236/1552},
     zbl = {0967.68172},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1552/}
}
TY  - JOUR
AU  - Eric Vigoda
TI  - A note on the Glauber dynamics for sampling independent sets
JO  - The electronic journal of combinatorics
PY  - 2001
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1552/
DO  - 10.37236/1552
ID  - 10_37236_1552
ER  - 
%0 Journal Article
%A Eric Vigoda
%T A note on the Glauber dynamics for sampling independent sets
%J The electronic journal of combinatorics
%D 2001
%V 8
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1552/
%R 10.37236/1552
%F 10_37236_1552

Cité par Sources :