The complexity of the majority rule on planar graphs

DOI10.1016/J.AAM.2014.11.005zbMath1319.68110OpenAlexW1981341508MaRDI QIDQ2255002

Pedro Montealegre, Eric Goles Chacc

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

computational complexityplanar graphmajorityNCP-completenessautomata networks

Mathematics Subject Classification ID

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

Related Items (5)

A Fast Parallel Algorithm for the Robust Prediction of the Two-Dimensional Strict Majority Automaton ⋮ On the complexity of two-dimensional signed majority cellular automata ⋮ The complexity of the asynchronous prediction of the majority automata ⋮ Freezing sandpiles and Boolean threshold networks: equivalence and complexity ⋮ Eric Goles

Cites Work

• Unnamed Item
• The complexity of the bootstraping percolation and other problems
• Decreasing energy functions as a tool for studying threshold networks
• Majority-vote cellular automata, Ising dynamics, and \(\mathbf P\)-completeness
• An ${\mathcal{N} \mathcal{C}}$ Algorithm for Evaluating Monotone Planar Circuits

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