
The Library
Propagation connectivity of random hypergraphs
Tools
Coja-Oghlan, Amin, Onsjoe, Mikael and Watanabe, Osamu (2012) Propagation connectivity of random hypergraphs. Electronic Journal of Combinatorics, Vol.19 . P17. ISSN 1077-8926.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://www.combinatorics.org/
Abstract
We study the concept of propagation connectivity on random 3-uniform hyper-graphs. 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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||
Journal or Publication Title: | Electronic Journal of Combinatorics | ||||
Publisher: | Electronic Journal of Combinatorics | ||||
ISSN: | 1077-8926 | ||||
Official Date: | 16 January 2012 | ||||
Dates: |
|
||||
Volume: | Vol.19 | ||||
Page Range: | P17 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |