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

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

doi:10.1016/j.biosystems.2009.11.004

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

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

Amsterdam Business Research Institute

Research output: Contribution to Journal › Article › Academic › peer-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 language	English
Pages (from-to)	210-214
Journal	BioSystems
Volume	99
DOIs	https://doi.org/10.1016/j.biosystems.2009.11.004
Publication status	Published - 2010

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1016/j.biosystems.2009.11.004

Persistent URL (handle)

Copy link address

Cite this

@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. {\textcopyright} 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",

}

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

SN - 0303-2647

VL - 99

SP - 210

EP - 214

JO - BioSystems

JF - BioSystems

ER -

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

Abstract

UN SDGs

Access to Document

Persistent URL (handle)

Fingerprint

Cite this