A note on the complexity of finding and enumerating elementary modes.

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.
Complete list of metadatas

https://hal.inria.fr/hal-00845385
Contributor : Marie-France Sagot <>
Submitted on : Wednesday, July 17, 2013 - 8:37:41 AM
Last modification on : Friday, September 27, 2019 - 10:10:18 AM

Links full text

Identifiers

Collections

Citation

Vicente Acuña, Alberto Marchetti-Spaccamela, Marie-France Sagot, Leen Stougie. A note on the complexity of finding and enumerating elementary modes.. BioSystems, Elsevier, 2010, 99 (3), pp.210-4. ⟨10.1016/j.biosystems.2009.11.004⟩. ⟨hal-00845385⟩

Share

Metrics

Record views

251