On time versus size for monotone dynamic monopolies in regular topologies

DOI10.1016/S1570-8667(03)00022-4zbMATH Open1074.68045MaRDI QIDQ1827282FDOQ1827282

Authors P. Flocchini, Rastislav Královič, Peter Ružička, Alessandro Roncato, N. Santoro

Publication date 6 August 2004

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Distributed computing Fault tolerance Majority rule

Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Games involving graphs (91A43) Distributed systems (68M14)

Recommendations

Dynamic monopolies in tori.
Tight bounds on the minimum size of a dynamic monopoly
Size bounds for dynamic monopolies
Bounding the number of tolerable faults in majority-based systems
Dynamic monopolies of constant size

Cites work

Local majorities, coalitions and monopolies in graphs: A review
Optimal irreversible dynamos in chordal rings
Size bounds for dynamic monopolies

Cited in

(45)

Opinion forming in Erdős-Rényi random graph and expanders
Majority rule cellular automata
On dynamic monopolies of graphs with probabilistic thresholds
On reversible cascades in scale-free and Erdős-Rényi random graphs
On irreversible spread of influence in edge-weighted graphs
Optimal irreversible dynamos in chordal rings
Irreversible conversion processes with deadlines
Modeling the spread of fault in majority-based network systems: dynamic monopolies in triangular grids
Triggering cascades on undirected connected graphs
Dynamic monopolies in tori.
On the complexity of reasoning about opinion diffusion under majority dynamics
Bounding the open \(k\)-monopoly number of strong product graphs
On dynamic monopolies of graphs: the average and strict majority thresholds
Spread of influence in weighted networks under time and budget constraints
Irreversible conversion of graphs
Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
Reversible iterative graph processes
On non-progressive spread of influence through social networks
Color War: Cellular Automata with Majority-Rule
scientific article; zbMATH DE number 1420911 (Why is no real title available?)
Influence Diffusion in Social Networks under Time Window Constraints
A study of monopolies in graphs
Spread of influence with incentives in edge-weighted graphs with emphasis on some families of graphs
The complexity of flood filling games
Fast and frugal targeting with incentives
Dynamic monopolies and feedback vertex sets in hexagonal grids
The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs
Dynamic monopolies in directed graphs: the spread of unilateral influence in social networks
Optimizing spread of influence in social networks via partial incentives
Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
Spreading of messages in random graphs
Latency-bounded target set selection in social networks
Triggering cascades on strongly connected directed graphs
An inclusion hierarchy of irreversible dynamos
Exact solutions for latency-bounded target set selection problem on some special families of graphs
Bounding the number of tolerable faults in majority-based systems
The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity
A computational study of \(f\)-reversible processes on graphs
Influence diffusion in social networks under time window constraints
Dynamic monopolies and feedback vertex sets in cycle permutation graphs, generalized Petersen graphs and torus cordalis
Multi-level dynamo and opinion spreading
On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold
Dynamic monopolies of constant size
Combinatorial model and bounds for target set selection
On dynamic monopolies of graphs with general thresholds

This page was built for publication: On time versus size for monotone dynamic monopolies in regular topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1827282)