Reversible iterative graph processes

DOI10.1016/J.TCS.2012.05.042zbMATH Open1254.05171OpenAlexW2080570447MaRDI QIDQ690472FDOQ690472

Authors Mitre C. Dourado, Lucia Draque Penso, Dieter Rautenbach, Jayme L. 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

zbMATH Keywords

consensusdynamic monopolyfinite discrete dynamical systemslocal majority processconquest and expansion gamesiterative polling processlocal interaction gamesreachability problems

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Irreversible conversion of graphs
• On \(f\)-reversible processes on graphs
• A computational study of \(f\)-reversible processes on graphs
• Dynamic monopolies in tori.
• Generalized threshold processes on graphs

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 2186652 (Why is no real title available?)
• scientific article; zbMATH DE number 4206005 (Why is no real title available?)
• scientific article; zbMATH DE number 2080927 (Why is no real title available?)
• A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem
• An improved testing scheme for catastrophic fault patterns
• Characterization of catastrophic faults in two-dimensional reconfigurable systolic arrays with unidirectional links
• Complexity of reachability problems for finite discrete dynamical systems
• Comportement périodique des fonctions à seuil binaires et applications
• Contagion
• Convergence to equilibrium in local interaction games
• Distributed probabilistic polling and applications to proportionate agreement
• Dynamic monopolies of constant size
• Fault-Local Distributed Mending
• General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• Listen to Your Neighbors: How (Not) to Reach a Consensus
• Local majorities, coalitions and monopolies in graphs: A review
• On an application of convexity to discrete systems
• On periodical behaviour in societies with symmetric influences
• On pre-periods of discrete influence systems
• On the Period-Two-Property of the Majority Operator in Infinite Graphs
• On the approximability of influence in social networks
• On time versus size for monotone dynamic monopolies in regular topologies
• Optimal irreversible dynamos in chordal rings
• Random majority percolation
• Size bounds for dynamic monopolies
• The power of small coalitions in graphs
• Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(8)

• Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree
• The interchange process with reversals on the complete graph
• Irreversible conversion of graphs
• Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system
• Generalized threshold processes on graphs
• On \(f\)-reversible processes on graphs
• A computational study of \(f\)-reversible processes on graphs
• The predecessor-existence problem for \(k\)-reversible processes

This page was built for publication: Reversible iterative graph processes

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