The complexity of the majority rule on planar graphs

Eric Goles; Pedro Montealegre

doi:10.1016/j.aam.2014.11.005

The complexity of the majority rule on planar graphs

Eric Goles
, Pedro Montealegre

Facultad de Ingeniería y Ciencias

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

9 Citas (Scopus)

Resumen

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.

Idioma original	Inglés
Páginas (desde-hasta)	111-123
Número de páginas	13
Publicación	Advances in Applied Mathematics
Volumen	64
N.º	1
DOI	https://doi.org/10.1016/j.aam.2014.11.005
Estado	Publicada - 2015

Acceder al documento

10.1016/j.aam.2014.11.005

Citar esto

@article{0080dabc71dd444ab0534557c24665e7,

title = "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.",

keywords = "Automata networks, Computational complexity, Majority, NC, P-Completeness, Planar graph",

author = "Eric Goles and Pedro Montealegre",

year = "2015",

doi = "10.1016/j.aam.2014.11.005",

language = "English",

volume = "64",

pages = "111--123",

journal = "Advances in Applied Mathematics",

issn = "0196-8858",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - The complexity of the majority rule on planar graphs

AU - Goles, Eric

AU - Montealegre, Pedro

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Automata networks

KW - Computational complexity

KW - Majority

KW - NC

KW - P-Completeness

KW - Planar graph

UR - https://www.scopus.com/pages/publications/84922733250

U2 - 10.1016/j.aam.2014.11.005

DO - 10.1016/j.aam.2014.11.005

M3 - Article

AN - SCOPUS:84922733250

SN - 0196-8858

VL - 64

SP - 111

EP - 123

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 1

ER -

The complexity of the majority rule on planar graphs

Resumen

Acceder al documento

Huella

Citar esto