The search functionality is under construction.

The search functionality is under construction.

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.3171^{n}) 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

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.

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.3171^{n}) 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.3171^{n}) 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.3171^{n}) 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 -