toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Record Links
Author (up) Goles, E.; Montealegre, P. pdf  doi
openurl 
  Title The complexity of the majority rule on planar graphs Type Journal Article
  Year 2015 Publication Advances In Applied Mathematics Abbreviated Journal Adv. Appl. Math.  
  Volume 64 Issue Pages 111-123  
  Keywords Automata networks; Computational complexity; Majority; P-Completeness; NC; Planar graph  
  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. (C) 2014 Elsevier Inc. All rights reserved.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl;  
  Corporate Author Thesis  
  Publisher Academic Press Inc Elsevier Science Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0196-8858 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000348883400007 Approved no  
  Call Number UAI @ eduardo.moreno @ Serial 445  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: