Dynamic monopolies of constant size

DOI10.1006/jctb.2001.2045zbMath1032.05052arXivmath/9911125OpenAlexW2170502901MaRDI QIDQ1850560

Eli Berger

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/9911125

zbMATH Keywords

votingfault handling in distributed systemsmajority processpolling gamesmall coalition

Mathematics Subject Classification ID

Games involving graphs (91A43) Coloring of graphs and hypergraphs (05C15)

Related Items (37)

Minority Becomes Majority in Social Networks ⋮ Diffusion in large networks ⋮ On non-progressive spread of influence through social networks ⋮ On dynamic monopolies of graphs with general thresholds ⋮ Combinatorial model and bounds for target set selection ⋮ Target set selection on generalized pancake graphs ⋮ Triggering cascades on undirected connected graphs ⋮ Majority vote in social networks ⋮ Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ Spreading of messages in random graphs ⋮ On dynamic monopolies of graphs: the average and strict majority thresholds ⋮ Treewidth governs the complexity of target set selection ⋮ Approximating fixation probabilities in the generalized Moran process ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ Majority rule cellular automata ⋮ Phase transition of the 2-choices dynamics on core-periphery networks ⋮ Triggering cascades on strongly connected directed graphs ⋮ Deprecation based greedy strategy for target set selection in large scale social networks ⋮ The effect of local majority on global majorityin connected graphs ⋮ Reversible iterative graph processes ⋮ The complexity of flood filling games ⋮ Irreversible conversion of graphs ⋮ Minimum 2-tuple dominating set of permutation graphs ⋮ Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis ⋮ A note on the majority dynamics in inhomogeneous random graphs ⋮ On the spread of influence in graphs ⋮ Absorption time of the Moran process ⋮ Opinion forming in Erdős-Rényi random graph and expanders ⋮ Opinion Forming in Erdös-Rényi Random Graph and Expanders ⋮ Spreading messages ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs ⋮ Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results ⋮ Majority dynamics and the retention of information ⋮ Unnamed Item ⋮ Local majorities, coalitions and monopolies in graphs: A review ⋮ An inclusion hierarchy of irreversible dynamos

Cites Work

• Unnamed Item
• Unnamed Item
• Periodic behaviour of generalized threshold functions
• Size bounds for dynamic monopolies
• The availability of quorum systems
• On periodical behaviour in societies with symmetric influences
• An O (log n ) expected rounds randomized byzantine generals protocol
• How to assign votes in a distributed system
• Fault Tolerance in Networks of Bounded Degree
• The Byzantine Generals Problem
• Fault-local distributed mending (extended abstract)

This page was built for publication: Dynamic monopolies of constant size