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
Martín Ríos-Wilson, Guillaume Theyssier, Eric Goles, Pedro Montealegre
Publication date: 22 March 2022
Full work available at URL: https://arxiv.org/abs/2005.11758
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
- Title not available (Why is that?)
- 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)
