IEICE TRANSACTIONS on Fundamentals
On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
Summary :
Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1771-1778
- Publication Date
- 2009/08/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E92.A.1771
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Theory
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Tatsuya AKUTSU, Takeyuki TAMURA, "On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2" in IEICE TRANSACTIONS on Fundamentals,
vol. E92-A, no. 8, pp. 1771-1778, August 2009, doi: 10.1587/transfun.E92.A.1771.
Abstract: Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1771/_p
Copy
@ARTICLE{e92-a_8_1771,
author={Tatsuya AKUTSU, Takeyuki TAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2},
year={2009},
volume={E92-A},
number={8},
pages={1771-1778},
abstract={Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.},
keywords={},
doi={10.1587/transfun.E92.A.1771},
ISSN={1745-1337},
month={August},}
Copy
TY - JOUR
TI - On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1771
EP - 1778
AU - Tatsuya AKUTSU
AU - Takeyuki TAMURA
PY - 2009
DO - 10.1587/transfun.E92.A.1771
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - Finding fixed points in discrete dynamical systems is important because fixed points correspond to steady-states. The Boolean network is considered as one of the simplest discrete dynamical systems and is often used as a model of genetic networks. It is known that detection of a fixed point in a Boolean network with n nodes and maximum indegree K can be polynomially transformed into (K+1)-SAT with n variables. In this paper, we focus on the case of K=2 and present an O(1.3171n) expected time algorithm, which is faster than the naive algorithm based on a reduction to 3-SAT, where we assume that nodes with indegree 2 do not contain self-loops. We also show an algorithm for the general case of K=2 that is slightly faster than the naive algorithm.
ER -
English
