Complexity of fixed point counting problems in Boolean networks
DOI10.1016/j.jcss.2022.01.004zbMath1483.68240arXiv2012.02513OpenAlexW3111725170MaRDI QIDQ2119407
Adrien Richard, Kévin Perrot, Florian Bridoux, Amélia Durbec
Publication date: 29 March 2022
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.02513
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Symbolic dynamics (37B10)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Combinatorics of Boolean automata circuits dynamics
- Complexity of limit-cycle problems in Boolean networks
- Dichotomy results for fixed-point existence problems for Boolean dynamical systems
- Maximum number of fixed points in regulatory Boolean networks
- Graphic requirements for multistability and attractive cycles in a Boolean dynamical framework
- An extension of a combinatorial fixed point theorem of Shih and Dong
- Topological fixed points in Boolean networks
- Asynchronous threshold networks
- A new fixed point approach for stable networks and stable marriages
- Cooperative Boolean systems with generically long attractors. II
- Positive and negative cycles in Boolean networks
- Fixed points and connections between positive and negative cycles in Boolean networks
- Pólya's permanent problem
- Fixed points and maximal independent sets in AND-OR networks
- Permanents, Pfaffian orientations, and even directed circuits
- Complexity of maximum fixed point problem in Boolean networks
- A new necessary condition on interaction graphs for multistationarity
- Maximum number of fixed points in AND-OR-NOT networks
- A lattice-theoretical fixpoint theorem and its applications
- Multistationarity, the basis of cell differentiation and memory. II. Logical analysis of regulatory networks in terms of feedback circuits
- Reduction and Fixed Points of Boolean Networks and Linear Network Coding Solvability
- Fixed Points of Boolean Networks, Guessing Graphs, and Coding Theory
- On the complexity of feedback set problems in signed digraphs
- Asynchronous Simulation of Boolean Networks by Monotone Boolean Networks
- Linear network coding
- Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications
- Cooperative Boolean systems with generically long attractors I
- Number of Fixed Points and Disjoint Cycles in Monotone Boolean Networks
- Depth-First Search and Linear Graph Algorithms
This page was built for publication: Complexity of fixed point counting problems in Boolean networks