The search functionality is under construction.
The search functionality is under construction.

On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2

Tatsuya AKUTSU, Takeyuki TAMURA

  • Full Text Views

    0

  • Cite this

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