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.
Liste complète des métadonnées

https://hal.inria.fr/hal-00845385
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 17 juillet 2013 - 08:37:41
Dernière modification le : jeudi 28 juin 2018 - 14:38:50

Lien texte intégral

Identifiants

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〉

Partager

Métriques

Consultations de la notice

181