Skip to Main content Skip to Navigation
Journal articles

The complexity of the majority rule on planar graphs

Abstract : We study the complexity of the majority rule on planar automata networks. We reduce a special case of the Monotone Circuit Value Problem to the prediction problem of determining if a vertex of a planar graph will change its state when the network is updated with the majority rule.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-01315322
Contributor : Pedro Montealegre <>
Submitted on : Friday, May 13, 2016 - 2:16:09 AM
Last modification on : Tuesday, November 19, 2019 - 4:46:01 PM

Links full text

Identifiers

Citation

Eric Goles Chacc, Pedro Montealegre. The complexity of the majority rule on planar graphs. Advances in Applied Mathematics, Elsevier, 2015, 64, pp.111-123. ⟨10.1016/j.aam.2014.11.005⟩. ⟨hal-01315322⟩

Share

Metrics

Record views

121