Minimal controllability of conjunctive Boolean networks is NP-complete

DOI10.1016/J.AUTOMATICA.2018.02.014zbMath1388.93022arXiv1704.07291OpenAlexW2610131202WikidataQ130096491 ScholiaQ130096491MaRDI QIDQ1642199

Guy Even, Michael Margaliot, Eyal Weiss

Publication date: 20 June 2018

Published in: Automatica (Search for Journal in Brave)

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

zbMATH Keywords

NP-completeconjunctive Boolean networksminimal controllability

Mathematics Subject Classification ID

Controllability (93B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Control/observation systems governed by functional relations other than differential equations (such as hybrid and switching systems) (93C30)

Related Items (7)

Set stability of switched delayed logical networks with application to finite-field consensus ⋮ Minimal observability of Boolean control networks ⋮ Design of reduced-order and pinning controllers for probabilistic Boolean networks using reinforcement learning ⋮ On the number of driver nodes for controlling a Boolean network when the targets are restricted to attractors ⋮ Distributional observability of probabilistic Boolean networks ⋮ Optimal reconstruction of noisy dynamics and selection probabilities in Boolean networks ⋮ Reduction and Analysis of Boolean Control Networks by Bisimulation

Cites Work

• Unnamed Item
• Unnamed Item
• Controllability of Boolean control networks via the Perron-Frobenius theory
• The dynamics of conjunctive and disjunctive Boolean network models
• Analysis and control of Boolean networks. A semi-tensor product approach.
• Stability structures of conjunctive Boolean networks
• Control of Boolean networks: hardness results and algorithms for tree structured networks
• Topological sorting of large networks
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Controllability of Conjunctive Boolean Networks With Application to Gene Regulation
• Minimal Controllability Problems
• Depth-First Search and Linear Graph Algorithms
• A survey of computational complexity results in systems and control

This page was built for publication: Minimal controllability of conjunctive Boolean networks is NP-complete