The Library
Propagation connectivity of random hypergraphs
Tools
Tools
Tools
Coja-Oghlan, Amin, Onsjoe, Mikael and Watanabe, Osamu (2010) Propagation connectivity of random hypergraphs. In: 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010), Univ Politecnica Catalunya (UPC), Barcelona, Spain, 01-03 Sep 2010. Published in: Lecture Notes in Computer Science, Vol.6302 pp. 490-503. ISBN 978-3-642-15368-6. doi:10.1007/978-3-642-15369-3_37 ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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: | Conference Item (Paper) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Journal or Publication Title: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer | ||||
| ISBN: | 978-3-642-15368-6 | ||||
| ISSN: | 0302-9743 | ||||
| Editor: | Serna, M and Shaltiel, R and Jansen, K and Rolim, J | ||||
| Official Date: | 2010 | ||||
| Dates: |
|
||||
| Volume: | Vol.6302 | ||||
| Number of Pages: | 14 | ||||
| Page Range: | pp. 490-503 | ||||
| DOI: | 10.1007/978-3-642-15369-3_37 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Conference Paper Type: | Paper | ||||
| Title of Event: | 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010)/14th International Workshop on Randomization and Computation (RANDOM 2010) | ||||
| Type of Event: | Workshop | ||||
| Location of Event: | Univ Politecnica Catalunya (UPC), Barcelona, Spain | ||||
| Date(s) of Event: | 01-03 Sep 2010 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
