On the impact of treewidth in the computational complexity of freezing dynamics

DOI10.1007/978-3-030-80049-9_24OpenAlexW3184362906MaRDI QIDQ2117789

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

Publication date: 22 March 2022

Full work available at URL: https://arxiv.org/abs/2005.11758

zbMATH Keywords

predictiontreewidthnilpotencyfast parallel algorithmasynchronous reachabilityfreezing automata networkspredecessor problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Cold dynamics in cellular automata: a tutorial ⋮ Eric Goles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple dynamics on graphs
• Fundamentals of parameterized complexity
• The complexity of the bootstraping percolation and other problems
• Computational complexity of finite asynchronous cellular automata
• Constraint satisfaction with bounded treewidth revisited
• Graph minors. V. Excluding a planar graph
• Universality in freezing cellular automata
• Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
• Cellular automata with sparse communication
• Bootstrap percolation in power-law random graphs
• On the stability and instability of finite dynamical systems with prescribed interaction graphs
• Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Polynomial Bounds for the Grid-Minor Theorem
• A Brief Tour of Theoretical Tile Self-Assembly
• Complexity of Finding Embeddings in a k-Tree
• Cellular graph automata. I. basic concepts, graph property measurement, closure properties
• The Nilpotency Problem of One-Dimensional Cellular Automata
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Directed Nowhere Dense Classes of Graphs
• Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata

This page was built for publication: On the impact of treewidth in the computational complexity of freezing dynamics