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

Text RH.pdf - Published Version Embargoed item. Restricted access to Repository staff only Download (250Kb)

Request Changes to record.

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, Engineering and Medicine > 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
Official Date:	1 September 2010
Dates:	Date Event 1 September 2010 Published
Number:	6302
Page Range:	pp. 490-503
DOI:	10.1007/978-3-642-15369-3_37
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Date of first compliant deposit:	21 December 2015

Request changes or add full text files to a record

Repository staff actions (login required)

View Item