toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
Author Goles, E.; Montealegre, P. pdf  doi
openurl 
  Title Computational complexity of threshold automata networks under different updating schemes Type
  Year 2014 Publication Theoretical Computer Science Abbreviated Journal Theor. Comput. Sci.  
  Volume 559 Issue Pages 3-19  
  Keywords Automata networks; Threshold functions; Computational complexity; Updating scheme; P-completeness; NC; NP-Hard  
  Abstract Given a threshold automata network, as well as an updating scheme over its vertices, we study the computational complexity associated with the prediction of the future state of a vertex. More precisely, we analyze two classes of local functions: the majority and the AND-OR rule (vertices take the AND or the OR logic functions over the state of its neighborhoods). Depending on the updating scheme, we determine the complexity class (NC, P, NP, PSPACE) where the prediction problem belongs. (C) 2014 Elsevier B.V. All rights reserved.  
  Address [Goles, Eric] Univ Adolfo Ibanez, Fac Ciencias & Tecnol, Santiago, Chile, Email: eric.chacc@uai.cl;  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0304-3975 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000347025300002 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 434  
Permanent link to this record
 

 
Author Li, B.; Moataz, F.Z.; Nisse, N.; Suchan, K. pdf  doi
openurl 
  Title Minimum size tree-decompositions Type
  Year 2018 Publication Discrete Applied Mathematics Abbreviated Journal Discret Appl. Math.  
  Volume 245 Issue Pages 109-127  
  Keywords Tree-decomposition; Treewidth; NP-hard  
  Abstract We study in this paper the problem of computing a tree-decomposition of a graph with width at most k and minimum number of bags. More precisely, we focus on the following problem: given a fixed k >= 1, what is the complexity of computing a tree-decomposition of width at most k with minimum number of bags in the class of graphs with treewidth at most k? We prove that the problem is NP-complete for any fixed k >= 4 and polynomial for k <= 2; for k = 3, we show that it is polynomial in the class of trees and 2-connected outerplanar graphs. (C) 2017 Elsevier B.V. All rights reserved.  
  Address [Moataz, Fatima Zahra; Nisse, Nicolas] INRIA, Rennes, France, Email: nicolas.nisse@inria.fr  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0166-218x ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000435046700011 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 874  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: