On the impact of treewidth in the computational complexity of freezing dynamics
From MaRDI portal
Publication:2117789
DOI10.1007/978-3-030-80049-9_24OpenAlexW3184362906MaRDI QIDQ2117789FDOQ2117789
Authors: Eric Goles, Pedro Montealegre, Martín Ríos-Wilson, Guillaume Theyssier 
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2005.11758
Recommendations
- On the computational complexity of the freezing non-strict majority automata
- Freezing, bounded-change and convergent cellular automata
- On the complexity of asynchronous freezing cellular automata
- Computational complexity of threshold automata networks under different updating schemes
- The complexity of the bootstraping percolation and other problems
predictiontreewidthnilpotencyfast parallel algorithmasynchronous reachabilityfreezing automata networkspredecessor problem
Cites Work
- Fundamentals of parameterized complexity
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Simple dynamics on graphs
- Can you beat treewidth?
- Complexity of Finding Embeddings in a k-Tree
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Computational complexity of finite asynchronous cellular automata
- Constraint satisfaction with bounded treewidth revisited
- Parallel Algorithms with Optimal Speedup for Bounded Treewidth
- Directed Nowhere Dense Classes of Graphs
- Bootstrap percolation in power-law random graphs
- The complexity of the bootstraping percolation and other problems
- Title not available (Why is that?)
- On the stability and instability of finite dynamical systems with prescribed interaction graphs
- Title not available (Why is that?)
- Cellular graph automata. I. basic concepts, graph property measurement, closure properties
- Generalized predecessor existence problems for Boolean finite dynamical systems on directed graphs
- Title not available (Why is that?)
- Cellular automata with sparse communication
- Universality in freezing cellular automata
- A brief tour of theoretical tile self-assembly
- Polynomial bounds for the grid-minor theorem
- Fast-Parallel Algorithms for Freezing Totalistic Asynchronous Cellular Automata
- Nilpotent dynamics on signed interaction graphs and weak converses of Thomas' rules
Cited In (2)
This page was built for publication: On the impact of treewidth in the computational complexity of freezing dynamics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117789)
