Reversible iterative graph processes
From MaRDI portal
Publication:690472
DOI10.1016/j.tcs.2012.05.042zbMath1254.05171MaRDI QIDQ690472
Lucia Draque Penso, Mitre C. Dourado, Dieter Rautenbach, Jayme Luiz Szwarcfiter
Publication date: 27 November 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.05.042
consensus; dynamic monopoly; finite discrete dynamical systems; local majority process; conquest and expansion games; iterative polling process; local interaction games; reachability problems
Related Items
On \(f\)-reversible processes on graphs, The predecessor-existence problem for \(k\)-reversible processes, A computational study of \(f\)-reversible processes on graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved testing scheme for catastrophic fault patterns
- Irreversible conversion of graphs
- Characterization of catastrophic faults in two-dimensional reconfigurable systolic arrays with unidirectional links
- Complexity of reachability problems for finite discrete dynamical systems
- Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
- On an application of convexity to discrete systems
- On pre-periods of discrete influence systems
- Comportement périodique des fonctions à seuil binaires et applications
- Size bounds for dynamic monopolies
- 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
- Distributed probabilistic polling and applications to proportionate agreement
- On periodical behaviour in societies with symmetric influences
- Random majority percolation
- On the Approximability of Influence in Social Networks
- Two-Processor Scheduling with Start-Times and Deadlines
- Fault-Local Distributed Mending
- Listen to Your Neighbors: How (Not) to Reach a Consensus
- General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
- On the Period-Two-Property of the Majority Operator in Infinite Graphs
- Contagion
- Convergence to Equilibrium in Local Interaction Games
- Optimal irreversible dynamos in chordal rings