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.
Type de document :
Article dans une revue
Advances in Applied Mathematics, Elsevier, 2015, 64, pp.111-123. 〈10.1016/j.aam.2014.11.005〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01315322
Contributeur : Pedro Montealegre <>
Soumis le : vendredi 13 mai 2016 - 02:16:09
Dernière modification le : mardi 20 septembre 2016 - 18:32:18

Identifiants

Collections

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〉

Partager

Métriques

Consultations de la notice

31