The complexity of the majority rule on planar graphs

DOI10.1016/J.AAM.2014.11.005MaRDI QIDQ2255002zbMATH OpenOpenAlexFDO

Authors Eric Goles, Pedro Montealegre

Publication date 6 February 2015

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.aam.2014.11.005

zbMATH Keywords

automata networkscomputational complexitymajorityNCP-completenessplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• PSPACE-completeness of majority automata networks
• The complexity of the asynchronous prediction of the majority automata
• The complexity of the bootstraping percolation and other problems
• Computational complexity of threshold automata networks under different updating schemes
• On the complexity of two-dimensional signed majority cellular automata

Cites work

• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits
• Decreasing energy functions as a tool for studying threshold networks
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Majority-vote cellular automata, Ising dynamics, and P-completeness
• The complexity of the bootstraping percolation and other problems

Cited in

(10)

• On the computational complexity of the freezing non-strict majority automata
• Freezing sandpiles and Boolean threshold networks: equivalence and complexity
• Eric Goles
• The complexity of the asynchronous prediction of the majority automata
• On the complexity of two-dimensional signed majority cellular automata
• The complexity of the bootstraping percolation and other problems
• A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton
• Computational complexity of threshold automata networks under different updating schemes
• Dynamical stability of threshold networks over undirected signed graphs
• PSPACE-completeness of majority automata networks

This page was built for publication: The complexity of the majority rule on planar graphs

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