Local majorities, coalitions and monopolies in graphs: A review
From MaRDI portal
Publication:1603713
DOI10.1016/S0304-3975(01)00055-XzbMath0997.68088OpenAlexW2066862787MaRDI QIDQ1603713
Publication date: 15 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00055-x
Related Items (82)
A polynomial time algorithm for geodetic hull number for complementary prisms ⋮ Global defensive sets in graphs ⋮ The size of graphs with given feedback vertex number ⋮ Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available ⋮ On the computational complexity of the Helly number in the \(P_3\) and related convexities ⋮ Hardness Results for Seeding Complex Contagion with Neighborhoods ⋮ On the \(P_3\)-hull number of some products of graphs ⋮ Target Set Selection in Dense Graph Classes ⋮ Minority Becomes Majority in Social Networks ⋮ Diffusion in large networks ⋮ On the harmless set problem parameterized by treewidth ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ Simple dynamics for plurality consensus ⋮ A study of monopolies in graphs ⋮ Integer programming models and algorithms for the graph decontamination problem with mobile agents ⋮ Dynamic monopolies in two-way bootstrap percolation ⋮ The power of small coalitions under two-tier majority on regular graphs ⋮ On non-progressive spread of influence through social networks ⋮ On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting? ⋮ On dynamic monopolies of graphs with general thresholds ⋮ New bounds on the decycling number of generalized de Bruijn digraphs ⋮ Combinatorial model and bounds for target set selection ⋮ Global defensive alliances of trees and Cartesian product of paths and cycles ⋮ Bounding the open \(k\)-monopoly number of strong product graphs ⋮ Local event boundary detection with unreliable sensors: analysis of the majority vote scheme ⋮ Target set selection on generalized pancake graphs ⋮ On dissemination thresholds in regular and irregular graph classes ⋮ Dynamic monopolies and feedback vertex sets in hexagonal grids ⋮ Triggering cascades on undirected connected graphs ⋮ On reversible cascades in scale-free and Erdős-Rényi random graphs ⋮ Spreading of messages in random graphs ⋮ Network decontamination under \(m\)-immunity ⋮ Multi-level dynamo and opinion spreading ⋮ On \(\alpha \)-domination in graphs ⋮ The decycling number of outerplanar graphs ⋮ Some results on the target set selection problem ⋮ Alliances in graphs: parameters, properties and applications -- a survey ⋮ Treewidth governs the complexity of target set selection ⋮ Unnamed Item ⋮ Irreversible conversion processes with deadlines ⋮ Latency-bounded target set selection in social networks ⋮ On the geodetic number of complementary prisms ⋮ Dynamic monopolies with randomized starting configuration ⋮ On the decycling number of generalized Kautz digraphs ⋮ Majority rule cellular automata ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Phase transition of the 2-choices dynamics on core-periphery networks ⋮ Triggering cascades on strongly connected directed graphs ⋮ A computational study of \(f\)-reversible processes on graphs ⋮ Parameterized approximability of maximizing the spread of influence in networks ⋮ The effect of local majority on global majorityin connected graphs ⋮ Reversible iterative graph processes ⋮ Constant thresholds can make target set selection tractable ⋮ Color War: Cellular Automata with Majority-Rule ⋮ Irreversible conversion of graphs ⋮ Near-optimal solutions for the generalized max-controlled set problem ⋮ The \(t\)-latency bounded strong target set selection problem in some kinds of special family of graphs ⋮ Unnamed Item ⋮ A lower bound on the $k$-conversion number of graphs of maximum degree $k+1$ ⋮ 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 ⋮ Whom to befriend to influence people ⋮ Feedback arc number and feedback vertex number of Cartesian product of directed cycles ⋮ Fast and frugal targeting with incentives ⋮ Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs ⋮ Opinion forming in Erdős-Rényi random graph and expanders ⋮ Opinion Forming in Erdös-Rényi Random Graph and Expanders ⋮ Global defensive alliances in star graphs ⋮ Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion ⋮ Spreading messages ⋮ On time versus size for monotone dynamic monopolies in regular topologies ⋮ Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results ⋮ On the complexity of reasoning about opinion diffusion under majority dynamics ⋮ The complexity of finding harmless individuals in social networks ⋮ Fixed points and 2-cycles of synchronous dynamic coloring processes on trees ⋮ Local interaction on random graphs ⋮ Influence diffusion in social networks under time window constraints ⋮ Spread of influence in weighted networks under time and budget constraints ⋮ Influence Diffusion in Social Networks under Time Window Constraints ⋮ On reconfigurability of target sets ⋮ An inclusion hierarchy of irreversible dynamos ⋮ Exact solutions for latency-bounded target set selection problem on some special families of graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Testing and reconfiguration of VLSI linear arrays
- Periodic behaviour of generalized threshold functions
- On a paper of Agur, Fraenkel and Klein
- On the ratio of optimal integral and fractional covers
- Ergodic theorems for weakly interacting infinite systems and the voter model
- Size bounds for dynamic monopolies
- The \(r\)-majority vote action on 0-1 sequences
- Parametrization for stationary patterns of the \(r\)-majority operators on 0-1 sequences
- Dynamic monopolies in tori.
- An analysis of the greedy algorithm for the submodular set covering problem
- Dynamic monopolies of constant size
- Distributed probabilistic polling and applications to proportionate agreement
- The availability of quorum systems
- On periodical behaviour in societies with symmetric influences
- Finite particle systems and infection models
- 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
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Fault-Local Distributed Mending
- Eigenvalues and expansion of regular graphs
- Tight Fault Locality
- An Optimal Synchronizer for the Hypercube
- Reaching a Consensus
- On the hardness of approximating minimization problems
- Time-adaptive self stabilization
This page was built for publication: Local majorities, coalitions and monopolies in graphs: A review
