Geodesic
Propagation connectivity of random hypergraphs
The electronic journal of combinatorics, Tome 19 (2012) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple propagation algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold. Our proof is based on a kind of large deviations analysis of a time-dependent random walk. Based on the analysis, we also give an upper bound on the expected running time of the simple propagation algorithm.
DOI : 10.37236/1168
Classification : 05C65, 05C80, 05C40, 05C85
Mots-clés : propagation algorithm, time-dependent random walk 
@article{10_37236_1168,
     author = {Amin Coja-Oghlan and Mikael Onsj\"o and Osamu Watanabe},
     title = {Propagation connectivity of random hypergraphs},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {1},
     doi = {10.37236/1168},
     zbl = {1244.05158},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1168/}
}
TY  - JOUR
AU  - Amin Coja-Oghlan
AU  - Mikael Onsjö
AU  - Osamu Watanabe
TI  - Propagation connectivity of random hypergraphs
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1168/
DO  - 10.37236/1168
ID  - 10_37236_1168
ER  - 
%0 Journal Article
%A Amin Coja-Oghlan
%A Mikael Onsjö
%A Osamu Watanabe
%T Propagation connectivity of random hypergraphs
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/1168/
%R 10.37236/1168
%F 10_37236_1168
Amin Coja-Oghlan; Mikael Onsjö; Osamu Watanabe. Propagation connectivity of random hypergraphs. The electronic journal of combinatorics, Tome 19 (2012) no. 1. doi: 10.37236/1168

Cité par Sources :