On the parameterized complexity of freezing dynamics

DOI10.1016/J.AAM.2024.102706MaRDI QIDQ6499443zbMATH OpenFDO

Authors Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier

Publication date 8 May 2024

Published in Advances in Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

treewidthprediction problemfast parallel algorithmsasynchronous reachabilityfreezing automata networkspredecessor problemnilpotency problem

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Cites work

• scientific article; zbMATH DE number 4058875 (Why is no real title available?)
• scientific article; zbMATH DE number 3718546 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 1241089 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 3382226 (Why is no real title available?)
• A brief tour of theoretical tile self-assembly
• Bootstrap percolation in power-law random graphs
• Bootstrap percolation on the hypercube
• Cellular automata with sparse communication
• Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems
• Complexity of Finding Embeddings in a k-Tree
• Computational Complexity
• Computational complexity of finite asynchronous cellular automata
• Constraint satisfaction with bounded treewidth revisited
• Counter machines and distributed automata -- a story about exchanging space and time
• Directed Nowhere Dense Classes of Graphs
• Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fundamentals of parameterized complexity
• Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
• Graph minors. V. Excluding a planar graph
• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• On the computational complexity of the freezing non-strict majority automata
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Polynomial bounds for the grid-minor theorem
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Simple dynamics on graphs
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The complexity of the bootstraping percolation and other problems
• The complexity of theorem-proving procedures
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The sharp threshold for bootstrap percolation in all dimensions
• Undirected connectivity in log-space
• Universality in freezing cellular automata

This page was built for publication: On the parameterized complexity of freezing dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499443)