| Records |
| Author |
Goles, E.; Montealegre, P. |
| 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. |
| 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 |
