A note on the complexity of finding and enumerating elementary modes |
| |
| Authors: | Vicente Acuñ a,Alberto Marchetti-Spaccamela,Marie-France Sagot,Leen Stougie |
| |
| Affiliation: | 1. Université de Lyon, F-69000 Lyon; Université Lyon 1; CNRS, UMR5558, Laboratoire de Biométrie et Biologie Evolutive, F-69622 Villeurbanne, France;2. INRIA Rhône-Alpes, 655 avenue de l’Europe, 38330 Montbonnot Saint-Martin, France;3. Universitá di Roma “La Sapienza”,Via Eudossiana 18, 00184 Rome, Italy;4. Vrije Universiteit Amsterdam, De Boelelaan 1105, 1081HV Amsterdam, The Netherlands;5. Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098SJ Amsterdam, The Netherlands |
| |
| 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. |
| |
| Keywords: | Metabolic networks Computational complexity Elementary modes Enumeration |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
