Triggering cascades on undirected connected graphs

DOI10.1016/j.ipl.2011.07.008zbMath1260.68292OpenAlexW2008428279MaRDI QIDQ1944178

Ching-Lueh Chang

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.07.008

zbMATH Keywords

fault tolerancefault propagationirreversible dynamic monopolyrepetitive polling gamelocal interaction gameirreversible conversion setreversible dynamic monopolyWatts model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (4)

Triggering cascades on strongly connected directed graphs ⋮ Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees ⋮ Whom to befriend to influence people ⋮ On the spread of influence in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial model and bounds for target set selection
• Spreading of messages in random graphs
• Bootstrap percolation on the hypercube
• Bootstrap percolation in three dimensions
• Minimal percolating sets in bootstrap percolation
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Spreading messages
• Metastable behavior for bootstrap percolation on regular trees
• Decreasing energy functions as a tool for studying threshold networks
• On an application of convexity to discrete systems
• The number of fixed points of the majority rule
• Almost exact minimum feedback vertex set in meshes and butterflies
• Periodic behaviour of generalized threshold functions
• On a paper of Agur, Fraenkel and Klein
• On the behavior of some cellular automata related to bootstrap percolation
• Size bounds for dynamic monopolies
• The statistical mechanics of strategic interaction
• The \(r\)-majority vote action on 0-1 sequences
• Parametrization for stationary patterns of the \(r\)-majority operators on 0-1 sequences
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Dynamic monopolies in tori.
• Local majorities, coalitions and monopolies in graphs: A review
• The power of small coalitions in graphs
• On time versus size for monotone dynamic monopolies in regular topologies
• Dynamic monopolies of constant size
• The majority action on infinite graphs: Strings and puppets
• On periodical behaviour in societies with symmetric influences
• The threshold regime of finite volume bootstrap percolation.
• Learning, Local Interaction, and Coordination
• Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
• Bootstrap percolation on the random regular graph
• NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
• Majority Bootstrap Percolation on the Hypercube
• Bounding the Number of Tolerable Faults in Majority-Based Systems
• A simple model of global cascades on random networks
• Random disease on the square grid
• On the Period-Two-Property of the Majority Operator in Infinite Graphs
• Bootstrap Percolation in High Dimensions
• Contagion
• Convergence to Equilibrium in Local Interaction Games
• Probability Inequalities for Sums of Bounded Random Variables
• Web Marshals Fighting Curly Link Farms
• Decycling Cartesian Products of Two Cycles
• Automata, Languages and Programming
• Variants of Spreading Messages
• Optimal irreversible dynamos in chordal rings

This page was built for publication: Triggering cascades on undirected connected graphs