Journal
MATHEMATICS IN COMPUTER SCIENCE
Volume 2, Issue 3, Pages 401-420Publisher
SPRINGER BASEL AG
DOI: 10.1007/s11786-008-0063-5
Keywords
Boolean network; fixed point; algorithm and planar graph
Categories
Funding
- MEXT
- NEDO, Japan
Ask authors/readers for more resources
Singleton attractor (also called fixed point) detection is known to be NP-hard even for AND/OR Boolean networks (AND/OR BNs in short, i.e., BNs consisting of AND/OR nodes), where BN is a mathematical model of genetic networks and singleton attractors correspond to steady states. In our recent paper, we developed an O(1.787(n)) time algorithm for detecting a singleton attractor of a given AND/OR BN where n is the number of nodes. In this paper, we present an O(1.757(n)) time algorithm with which we succeeded in improving the above algorithm. We also show that this problem can be solved in 2(O((log n)root n)) time, which is less than O((1 + epsilon)n) for any positive constant epsilon, when a BN is planar.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available