All of RECERCAT

This Collection

Use this identifier to quote or link this document: http://hdl.handle.net/2072/81199

Title:	Propagation connectivity of random hypergraphs
Author:	Coja-Oghlan, Amin; Onsjö, Mikael; Watanabe, Osamu
Other authors:	Centre de Recerca Matemàtica
Resum:	We study the concept of propagation connectivity on random 3-uniform hypergraphs. This concept is inspired by a simple linear time algorithm for solving instances of certain constraint satisfaction problems. We derive upper and lower bounds for the propagation connectivity threshold, and point out some algorithmic implications.
Creation date:	2010-05
Subject (UDC):	519.1 - Teoria general de l'anàlisi combinatòria. Teoria de grafs
Subject(s):	Hipergrafs
Rights:	Aquest document està subjecte a una llicència d'ús de Creative Commons, amb la qual es permet copiar, distribuir i comunicar públicament l'obra sempre que se'n citin l'autor original, la universitat i el centre i no se'n faci cap ús comercial ni obra derivada, tal com queda estipulat en la llicència d'ús (http://creativecommons.org/licenses/by-nc-nd/2.5/es/)
Document type:	Preprint
Share:

Files	Size	Format
Pr948.pdf	262.6 KB	PDF