A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2 Ao encontrar um ponto fixo em uma rede booleana com grau de entrada máximo 2

Tatsuya AKUTSU, Takeyuki TAMURA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Encontrar pontos fixos em sistemas dinâmicos discretos é importante porque os pontos fixos correspondem a estados estacionários. A rede booleana é considerada um dos sistemas dinâmicos discretos mais simples e é frequentemente usada como modelo de redes genéticas. Sabe-se que a detecção de um ponto fixo em uma rede booleana com n nós e grau máximo K pode ser transformado polinomialmente em (K+1)-SAT com n variáveis. Neste artigo, nos concentramos no caso de K=2 e apresente um O(1.3171n) algoritmo de tempo esperado, que é mais rápido que o algoritmo ingênuo baseado em uma redução para 3-SAT, onde assumimos que os nós com grau 2 não contêm auto-loops. Também mostramos um algoritmo para o caso geral de K=2 que é um pouco mais rápido que o algoritmo ingênuo.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1771-1778
Data de publicação
2009/08/01
Publicitada
ISSN online
1745-1337
DOI
10.1587/transfun.E92.A.1771
Tipo de Manuscrito
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Categoria
Teoria

autores

Palavra-chave