In the context of the study into elementary modes of metabolic networks, we prove two complexity results. Enumerating elementary modes containing a specific reaction is hard in an enumeration complexity sense. The decision problem if there exists an elementary mode containing two specific reactions is NP-complete. The complexity of enumerating all elementary modes remains open. (C) 2009 Elsevier Ireland Ltd. All rights reserved.
A note on the complexity of finding and enumerating elementary modes / Vicente, Acuna; MARCHETTI SPACCAMELA, Alberto; Marie France, Sagot; Leen, Stougie. - In: BIOSYSTEMS. - ISSN 0303-2647. - 99:3(2010), pp. 210-214. [10.1016/j.biosystems.2009.11.004]
A note on the complexity of finding and enumerating elementary modes
MARCHETTI SPACCAMELA, Alberto;
2010
Abstract
In the context of the study into elementary modes of metabolic networks, we prove two complexity results. Enumerating elementary modes containing a specific reaction is hard in an enumeration complexity sense. The decision problem if there exists an elementary mode containing two specific reactions is NP-complete. The complexity of enumerating all elementary modes remains open. (C) 2009 Elsevier Ireland Ltd. All rights reserved.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2009_11573-90750.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
335.47 kB
Formato
Adobe PDF
|
335.47 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
