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

Faculty of Engineering and Science

Research output: Contribution to journal › Article › peer-review

8 Scopus citations

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.

Original language	English
Pages (from-to)	111-123
Number of pages	13
Journal	Advances in Applied Mathematics
Volume	64
Issue number	1
DOIs	https://doi.org/10.1016/j.aam.2014.11.005
State	Published - 2015

Keywords

Automata networks
Computational complexity
Majority
NC
P-Completeness
Planar graph

Access to Document

10.1016/j.aam.2014.11.005

Cite this

@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 - http://www.scopus.com/inward/record.url?scp=84922733250&partnerID=8YFLogxK

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this