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)

zbMATH Keywords

Distributed computingFault toleranceMajority rule

Mathematics Subject Classification ID

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)