On dissemination thresholds in regular and irregular graph classes

DOI10.1007/s00453-009-9309-0zbMath1213.68468OpenAlexW2069366387WikidataQ62046049 ScholiaQ62046049MaRDI QIDQ627518

Karol Suchan, Ioan Todinca, Ivan Rapaport, Jacques Verstraete

Publication date: 2 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9309-0

zbMATH Keywords

cubic graphsinformation disseminationbootstrap percolation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Strong-majority bootstrap percolation on regular graphs with low dissemination threshold ⋮ The complexity of the bootstraping percolation and other problems ⋮ Communication complexity meets cellular automata: necessary conditions for intrinsic universality ⋮ Strict majority bootstrap percolation in the \textit{r}-wheel ⋮ Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Global defensive alliances in graphs
• Local majorities, coalitions and monopolies in graphs: A review
• The threshold regime of finite volume bootstrap percolation.
• Bootstrap percolation on the random regular graph
• Small Alliances in Graphs
• Majority Bootstrap Percolation on the Hypercube
• Girth of sparse graphs
• Metastability effects in bootstrap percolation
• Algorithms – ESA 2005