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

Metabolic Networks and Pathways
Ireland
Metabolic Network
Decision problem
Enumeration
NP-complete problem

Cite this

Acuna, V. ; Marchetti-Spaccamela, A. ; Sagot, M.-F. ; Stougie, L. / A note on the complexity of finding and enumerating elementary modes. In: BioSystems. 2010 ; Vol. 99. pp. 210-214.
@article{ac45b406edc447daa891e80ad6ae195b,
title = "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. {\circledC} 2009 Elsevier Ireland Ltd.",
author = "V. Acuna and A. Marchetti-Spaccamela and M.-F. Sagot and L. Stougie",
year = "2010",
doi = "10.1016/j.biosystems.2009.11.004",
language = "English",
volume = "99",
pages = "210--214",
journal = "BioSystems",
issn = "0303-2647",
publisher = "Elsevier Ireland Ltd",

}

A note on the complexity of finding and enumerating elementary modes. / Acuna, V.; Marchetti-Spaccamela, A.; Sagot, M.-F.; Stougie, L.

In: BioSystems, Vol. 99, 2010, p. 210-214.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

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

AU - Acuna, V.

AU - Marchetti-Spaccamela, A.

AU - Sagot, M.-F.

AU - Stougie, L.

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

U2 - 10.1016/j.biosystems.2009.11.004

DO - 10.1016/j.biosystems.2009.11.004

M3 - Article

VL - 99

SP - 210

EP - 214

JO - BioSystems

JF - BioSystems

SN - 0303-2647

ER -