The Library
Propagation connectivity of random hypergraphs
Tools
Tools
Tools
Coja-Oghlan, Amin, Onsjö, M. and Watanabe, O. (2010) Propagation connectivity of random hypergraphs. In: Approximation, Randomization, and Combinatorial Optimization. Lecture Notes in Computer Science (6302). London: Springer Verlag, pp. 490-503. ISBN 9783642153686
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/978-3-642-15369-3_37
Abstract
We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is defined for investigating the performance of a simple algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for edge probability of random 3-uniform hypergraphs such that the propagation connectivity holds. Based on our analysis, we also show the way to implement the simple algorithm so that it runs in linear time on average.
| Item Type: | Book Item |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Journal or Publication Title: | Lecture Notes in Computer Science |
| Publisher: | Springer Verlag |
| Place of Publication: | London |
| ISBN: | 9783642153686 |
| ISSN: | 0302-9743 |
| Book Title: | Approximation, Randomization, and Combinatorial Optimization |
| Date: | 1 September 2010 |
| Number: | 6302 |
| Page Range: | pp. 490-503 |
| Identification Number: | 10.1007/978-3-642-15369-3_37 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Access rights to Published version: | Restricted or Subscription Access |
| Related URLs: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47418 |
Actions (login required)
 |
View Item |
