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

V. Acuna, A. Marchetti-Spaccamela, M.-F. Sagot, L. Stougie

Research output: Contribution to JournalArticleAcademicpeer-review

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. © 2009 Elsevier Ireland Ltd.
Original languageEnglish
Pages (from-to)210-214
JournalBioSystems
Volume99
DOIs
Publication statusPublished - 2010

Fingerprint

Dive into the research topics of 'A note on the complexity of finding and enumerating elementary modes.'. Together they form a unique fingerprint.

Cite this