{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T18:25:18Z","timestamp":1763663118284},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math.Comput.Sci."],"published-print":{"date-parts":[[2013,9]]},"DOI":"10.1007\/s11786-013-0160-y","type":"journal-article","created":{"date-parts":[[2013,10,14]],"date-time":"2013-10-14T00:11:22Z","timestamp":1381709482000},"page":"275-292","source":"Crossref","is-referenced-by-count":3,"title":["On the Complexity of Reconstructing Chemical Reaction Networks"],"prefix":"10.1007","volume":"7","author":[{"given":"Rolf","family":"Fagerberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Flamm","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Merkle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philipp","family":"Peters","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,10,15]]},"reference":[{"key":"160_CR1","unstructured":"Limboole. http:\/\/fmv.jku.at\/limboole\/index.html . Institute for Formal Models and Verification (2013)"},{"key":"160_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Galil, Z., Margalit, O., Naor, M.: Witnesses for boolean matrix multiplication and for shortest paths. In: Foundations of Computer Science, 1992. Proceedings of 33rd Annual Symposium, pp. 417\u2013426. IEEE (1992)","DOI":"10.1109\/SFCS.1992.267748"},{"key":"160_CR3","doi-asserted-by":"crossref","unstructured":"Andersen, J., Flamm, C., Merkle, D., Stadler P.: Maximizing output and recognizing autocatalysis in chemical reaction networks is NP-complete. J. Syst. Chem. 3(1) (2012)","DOI":"10.1186\/1759-2208-3-1"},{"key":"160_CR4","unstructured":"Barrett, C., Stump, A., Tinelli, C.: The SMT-LIB Standard: Version 2.0. In: Gupta, A., Kroening, D. (eds.) Proceedings of the 8th International Workshop on Satisfiability Modulo Theories (Edinburgh, UK) (2010)"},{"key":"160_CR5","first-page":"71","volume":"15","author":"G. Benk\u00f6","year":"2009","unstructured":"Benk\u00f6 G., Centler F., Dittrich P., Flamm C., Stadler B.M.R., Stadler P.F.: A topological approach to chemical organizations. Alife 15, 71\u201388 (2009)","journal-title":"Alife"},{"key":"160_CR6","unstructured":"Biere, A.: Lingeling, plingeling, picosat and precosat at sat race 2010. FMV Report Series Technical Report 10(1) (2010)"},{"key":"160_CR7","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T.: Handbook of Satisfiability, Frontiers in Artificial Intelligence and Applications, vol. 185 (2009)"},{"key":"160_CR8","doi-asserted-by":"crossref","unstructured":"Borenstein, E., Kupiec, M., Feldman, M.W., Ruppin, E.: Large-scale reconstruction and phylogenetic analysis of metabolic environments. Proc. Natl. Acad. Sci. USA 105, 14482\u201314487 (2008)","DOI":"10.1073\/pnas.0806162105"},{"issue":"3","key":"160_CR9","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1002\/jgt.3190020313","volume":"2","author":"M. Capobianco","year":"1978","unstructured":"Capobianco M., Molluzzo J.C.: Examples and counterexamples in graph theory. J. Graph Theory 2(3), 274\u2013274 (1978)","journal-title":"J. Graph Theory"},{"key":"160_CR10","doi-asserted-by":"crossref","unstructured":"Cottret, L., Wildridge, D., Vinson, F., Barrett, M.P., Charles, H., Sagot, M.-F., Jourdan, F.: Metexplore: a web server to link metabolomic experiments and genome-scale metabolic networks. Nucleic Acids Res. 38(suppl 2), W132\u2013W137 (2010)","DOI":"10.1093\/nar\/gkq312"},{"key":"160_CR11","doi-asserted-by":"crossref","first-page":"1321","DOI":"10.1137\/050634177","volume":"66","author":"G. Craciun","year":"2006","unstructured":"Craciun G., Feinberg M.: Multiple equilibria in complex chemical reaction networks: II. The species-reaction graph. SIAM J. Appl. Math. 66, 1321\u20131338 (2006)","journal-title":"SIAM J. Appl. Math."},{"issue":"4963","key":"160_CR12","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/978-3-540-78800-3_24","volume":"08","author":"L. De Moura","year":"2008","unstructured":"De Moura L., Bj\u00f8rner N.: Z3: An efficient SMT solver. Tools Algorithms Constr. Anal. Syst. (TACAS\u2019) 08(4963), 337\u2013340 (2008)","journal-title":"Tools Algorithms Constr. Anal. Syst. (TACAS\u2019)"},{"key":"160_CR13","doi-asserted-by":"crossref","first-page":"295","DOI":"10.3934\/nhm.2008.3.295","volume":"3","author":"M. Domijan","year":"2008","unstructured":"Domijan M., Kirkilionis M.: Graph theory and qualitative analysis of reaction networks. Netw. Heterog. Media 3, 295\u2013322 (2008)","journal-title":"Netw. Heterog. Media"},{"key":"160_CR14","doi-asserted-by":"crossref","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible sat-solver. In: Theory and Applications of Satisfiability Testing, pp. 333\u2013336. Springer, New York (2004)","DOI":"10.1007\/978-3-540-24605-3_37"},{"key":"160_CR15","first-page":"17","volume":"5","author":"P. Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P., R\u00e9nyi A.: On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl 5, 17\u201361 (1960)","journal-title":"Magyar Tud. Akad. Mat. Kutat\u00f3 Int. K\u00f6zl"},{"key":"160_CR16","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF00255665","volume":"49","author":"M. Feinberg","year":"1972","unstructured":"Feinberg M.: Complex balancing in general kinetic systems. Arch. Ration. Mech. Anal. 49, 187\u2013194 (1972)","journal-title":"Arch. Ration. Mech. Anal."},{"issue":"2","key":"160_CR17","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G. Gallo","year":"1993","unstructured":"Gallo G., Longo G., Pallottino S., Nguyen S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177\u2013201 (1993)","journal-title":"Discrete Appl. Math."},{"key":"160_CR18","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness (1979)"},{"issue":"6995","key":"160_CR19","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1038\/nature02555","volume":"430","author":"J.D.J. Han","year":"2004","unstructured":"Han J.D.J., Bertin N., Hao T., Goldberg D.S., Berriz G.F., Zhang L.V., Dupuy D., Walhout A.J., Cusick M.E., Roth F.P. et\u00a0al.: Evidence for dynamically organized modularity in the yeast protein\u2013protein interaction network. Nature 430(6995), 88\u201393 (2004)","journal-title":"Nature"},{"key":"160_CR20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF00251225","volume":"47","author":"F.J.M. Horn","year":"1972","unstructured":"Horn F.J.M., Jackson R.: General mass action kinetics. Arch. Ration. Mech. Anal. 47, 81\u2013116 (1972)","journal-title":"Arch. Ration. Mech. Anal."},{"key":"160_CR21","first-page":"1019","volume":"20","author":"A.N. Ivanova","year":"1979","unstructured":"Ivanova A.N.: Conditions for uniqueness of stationary state of kinetic systems, related, to structural scheme of reactions. Kinet. Katal 20, 1019\u20131023 (1979)","journal-title":"Kinet. Katal"},{"issue":"6804","key":"160_CR22","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1038\/35036627","volume":"407","author":"H. Jeong","year":"2000","unstructured":"Jeong H., Tombor B., Albert R., Oltvai Z., Barab\u00e1si A.: The large-scale organization of metabolic networks. Nature 407(6804), 651\u2013654 (2000)","journal-title":"Nature"},{"key":"160_CR23","unstructured":"Kaltenbach, H.-M.: A unified view on bipartite species-reaction and interaction graphs for chemical reaction networks. Technical Report 1210.0320, arXiv (2012)"},{"key":"160_CR24","doi-asserted-by":"crossref","unstructured":"Klamt S, Haus U-U, Theis F (2009) Hypergraphs and cellular networks. PLoS Comput Biol 5:e1000385","DOI":"10.1371\/journal.pcbi.1000385"},{"issue":"4","key":"160_CR25","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1109\/TCBB.2008.79","volume":"5","author":"V. Lacroix","year":"2008","unstructured":"Lacroix V., Cottret L., Th\u00e9bault P., Sagot M.: An introduction to metabolic networks and their structural analysis. IEEE\/ACM Trans. Comput. Biol. Bioinforma. 5(4), 594\u2013617 (2008)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinforma."},{"key":"160_CR26","unstructured":"McNaught, A., Wilkinson, A.: IUPAC. Compendium of Chemical Terminology, vol. 2. Blackwell Scientific Publications, Oxford (1997)"},{"issue":"10","key":"160_CR27","doi-asserted-by":"crossref","first-page":"1348","DOI":"10.1109\/TKDE.2008.53","volume":"20","author":"P. Miettinen","year":"2008","unstructured":"Miettinen P., Mielikainen T., Gionis A., Das G., Mannila H.: The discrete basis problem. IEEE Trans. Knowl. Data Eng. 20(10), 1348\u20131362 (2008)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"160_CR28","doi-asserted-by":"crossref","first-page":"204102","DOI":"10.1063\/1.2397073","volume":"125","author":"M. Mincheva","year":"2006","unstructured":"Mincheva M., Roussel M.R.: A graph-theoretic method for detecting potential Turing bifurcations. J. Chem. Phys 125, 204102 (2006)","journal-title":"J. Chem. Phys"},{"key":"160_CR29","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s00285-007-0099-1","volume":"55","author":"M. Mincheva","year":"2007","unstructured":"Mincheva M., Roussel M.R.: Graph-theoretic methods for the analysis of chemical and biochemical networks. I. Multistability and oscillations in ordinary differential equation models. J. Math. Biol. 55, 61\u201368 (2007)","journal-title":"J. Math. Biol."},{"key":"160_CR30","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.mbs.2012.08.002","volume":"241","author":"G. Shinar","year":"2013","unstructured":"Shinar G., Feinberg M.: Concordant chemical reaction networks and the species-reaction graph. Math. Biosci. 241, 1\u201323 (2013)","journal-title":"Math. Biosci."},{"key":"160_CR31","unstructured":"Skiena, S.: Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (1990)"},{"key":"160_CR32","unstructured":"S\u00f6rensson, N., E\u00e9n, N.: Minisat v1. 13-a sat solver with conflict-clause minimization. SAT 2005, 53 (2005)"},{"key":"160_CR33","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1159\/000076100","volume":"1","author":"C. Soul\u00e9","year":"2003","unstructured":"Soul\u00e9 C.: Graphic requirements for multistationarity. ComplexUs 1, 123\u2013133 (2003)","journal-title":"ComplexUs"},{"issue":"16","key":"160_CR34","doi-asserted-by":"crossref","first-page":"168101","DOI":"10.1103\/PhysRevLett.94.168101","volume":"94","author":"R. Tanaka","year":"2005","unstructured":"Tanaka R.: Scale-rich metabolic networks. Phys. Rev. Lett. 94(16), 168101 (2005)","journal-title":"Phys. Rev. Lett."},{"key":"160_CR35","doi-asserted-by":"crossref","unstructured":"Thomas, R.: On the relation between the logical structure of systems and their ability to generate multiple steady states or sustained oscillations. In: Della Dora, J., Demongeot, J., Lacolle, B. (eds.) Numerical Methods in the Study of Critical Phenomena, vol. 9, pp. 180\u2013193. Springer, Berlin (1981)","DOI":"10.1007\/978-3-642-81703-8_24"},{"key":"160_CR36","doi-asserted-by":"crossref","unstructured":"Tseitin, G.: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics (translated from Russian), Steklov Mathematical Institute, pp. 115\u2013125 (1968)","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"160_CR37","first-page":"466","volume":"2","author":"G. Tseitin","year":"1983","unstructured":"Tseitin G.: On the complexity of derivation in propositional calculus. Autom. Reason. Class. Papers Comput. Logic 2, 466\u2013483 (1983)","journal-title":"Autom. Reason. Class. Papers Comput. Logic"},{"key":"160_CR38","unstructured":"Volpert, A., Ivanova, A.N.: Mathematical models in chemical kinetics. In: Mathematical Modeling, pp. 57\u2013102. Nauka, Moscow (1987) (Russian)"},{"key":"160_CR39","doi-asserted-by":"crossref","first-page":"1803","DOI":"10.1098\/rspb.2001.1711","volume":"268","author":"A. Wagner","year":"2001","unstructured":"Wagner A., Fell D.A.: The small world inside large metabolic networks. Proc. R. Soc. Lond. B 268, 1803\u20131810 (2001)","journal-title":"Proc. R. Soc. Lond. B"},{"key":"160_CR40","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1038\/30918","volume":"393","author":"D.J. Watts","year":"1998","unstructured":"Watts D.J., Strogatz S.H.: Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 409\u2013410 (1998)","journal-title":"Nature"},{"key":"160_CR41","doi-asserted-by":"crossref","unstructured":"Zeigarnik, A.V.: On hypercycles and hypercircuits in hypergraphs. In: Hansen, P., Fowler, P.W., Zheng, M. (eds.) Discrete Mathematical Chemistry, volume 51 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 377\u2013383. American Mathematical Society, Providence (2000)","DOI":"10.1090\/dimacs\/051\/28"}],"container-title":["Mathematics in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-013-0160-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11786-013-0160-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11786-013-0160-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T15:59:00Z","timestamp":1564502340000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11786-013-0160-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["160"],"URL":"https:\/\/doi.org\/10.1007\/s11786-013-0160-y","relation":{},"ISSN":["1661-8270","1661-8289"],"issn-type":[{"value":"1661-8270","type":"print"},{"value":"1661-8289","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}