2012年1月
Singleton and 2-periodic attractors of sign-definite Boolean networks
INFORMATION PROCESSING LETTERS
- ,
- ,
- 巻
- 112
- 号
- 1-2
- 開始ページ
- 35
- 終了ページ
- 38
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.ipl.2011.10.002
- 出版者・発行元
- ELSEVIER SCIENCE BV
Although it is in general NP-hard to find a singleton attractor of a sign-definite network, if the network is strongly connected and has no directed negative cycle then it has at least two singleton attractors that can be found in polynomial time, as proved by Aracena. We describe an algorithm for finding a singleton attractor of a sign-definite network which does not have a directed negative cycle but is not necessarily strongly connected. The algorithm is not only much simpler than the algorithm of Goles and Salinas for the same problem, but also, unlike their algorithm, runs in polynomial time. It was proven by Just that the problem of finding a 2-periodic attractor is in a sense harder yet, because it remains NP-hard for a positive network. We prove, however, that if the positive network has a source strongly connected component devoid of odd cycles, then it is possible to find a 2-periodic attractor in polynomial-time, and we present an algorithm for doing so. (C) 2011 Elsevier B.V. All rights reserved.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.ipl.2011.10.002
- DBLP
- https://dblp.uni-trier.de/rec/journals/ipl/AkutsuMT12
- J-GLOBAL
- https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201102279025585342
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000298209700008&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/journals/ipl/ipl112.html#journals/ipl/AkutsuMT12
- ID情報
-
- DOI : 10.1016/j.ipl.2011.10.002
- ISSN : 0020-0190
- DBLP ID : journals/ipl/AkutsuMT12
- J-Global ID : 201102279025585342
- Web of Science ID : WOS:000298209700008