{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T10:13:06Z","timestamp":1781345586665,"version":"3.54.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,6]],"date-time":"2014-11-06T00:00:00Z","timestamp":1415232000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s10208-014-9231-y","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T14:46:45Z","timestamp":1415976405000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees"],"prefix":"10.1007","volume":"16","author":[{"given":"Sergey","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dima","family":"Grigoriev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gleb","family":"Koshevoy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,11,6]]},"reference":[{"key":"9231_CR1","unstructured":"A. Aho, J. Hopcroft, and J. Ullman, The design and analysis of computer algorithms, Addison-Wesley, 1975."},{"key":"9231_CR2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1006\/aima.1996.0057","volume":"122","author":"A Berenstein","year":"1996","unstructured":"A. Berenstein, S. Fomin, and A. Zelevinsky, Parametrizations of canonical bases and totally positive matrices, Adv. Math. 122 (1996), 49\u2013149.","journal-title":"Adv. Math."},{"key":"9231_CR3","doi-asserted-by":"crossref","unstructured":"P. B\u00fcrgisser, M. Clausen, and M. A. Shokrollahi, Algebraic complexity theory, Springer-Verlag, 1997.","DOI":"10.1007\/978-3-662-03338-8"},{"key":"9231_CR4","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s, Modern graph theory, Springer, 1998.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"9231_CR5","unstructured":"C. Chan, V. Drensky, A. Edelman, R. Kan, and P. Koev, On computing Schur functions and series thereof, preprint, 2008."},{"key":"9231_CR6","doi-asserted-by":"crossref","unstructured":"W.-K. Chen, Graph theory and its engineering applications, World Scientific, 1997.","DOI":"10.1142\/2446"},{"key":"9231_CR7","doi-asserted-by":"crossref","unstructured":"V. I. Danilov, A. V. Karzanov, and G. A. Koshevoy, Systems of separated sets and their geometric models, Uspehi Mat. Nauk, 65 (2010), 67-152 (in Russian); English translation in Russian Math. Surveys 65 (2010), no. 4, 659\u2013740.","DOI":"10.1070\/RM2010v065n04ABEH004692"},{"issue":"1\u20133","key":"9231_CR8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0024-3795(99)00134-2","volume":"299","author":"J Demmel","year":"1999","unstructured":"J. Demmel, M. Gu, S. Eisenstat, I. Slapni\u010dar, K. Veseli\u0107, and Z. Drma\u010d, Computing the singular value decomposition with high relative accuracy, Linear Algebra Appl. 299 (1999), no. 1-3, 21\u201380.","journal-title":"Linear Algebra Appl."},{"issue":"253","key":"9231_CR9","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1090\/S0025-5718-05-01780-1","volume":"75","author":"J Demmel","year":"2006","unstructured":"J. Demmel and P. Koev, Accurate and efficient evaluation of Schur and Jack functions, Math. Comp. 75 (2006), no. 253, 223\u2013239.","journal-title":"Math. Comp."},{"key":"9231_CR10","doi-asserted-by":"crossref","unstructured":"S. Fomin, Total positivity and cluster algebras, Proceedings of the International Congress of Mathematicians. Volume II, 125\u2013145, Hindustan Book Agency, 2010.","DOI":"10.1142\/9789814324359_0043"},{"key":"9231_CR11","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1090\/S0894-0347-01-00385-X","volume":"15","author":"S Fomin","year":"2002","unstructured":"S. Fomin and A. Zelevinsky, Cluster algebras\u00a0I: Foundations, J. Amer. Math. Soc., 15, (2002), 497\u2013529.","journal-title":"J. Amer. Math. Soc."},{"key":"9231_CR12","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1006\/jabr.1994.1361","volume":"170","author":"I Goulden","year":"1994","unstructured":"I. Goulden and C. Greene, A new tableau representation for supersymmetric Schur functions, J. Algebra 170 (1994), 687\u2013703.","journal-title":"J. Algebra"},{"key":"9231_CR13","doi-asserted-by":"crossref","first-page":"1388","DOI":"10.1007\/BF02104745","volume":"29","author":"D Grigoriev","year":"1985","unstructured":"D. Grigoriev, Lower bounds in algebraic complexity, J. Soviet Math. 29 (1985), 1388\u20131425.","journal-title":"J. Soviet Math."},{"key":"9231_CR14","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0168-0072(01)00055-0","volume":"113","author":"D Grigoriev","year":"2002","unstructured":"D. Grigoriev and N. Vorobjov, Complexity of Null- and Positivstellensatz proofs, Ann. Pure Appl. Logic 113 (2002), 153\u2013160.","journal-title":"Ann. Pure Appl. Logic"},{"key":"9231_CR15","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1145\/322326.322341","volume":"29","author":"M Jerrum","year":"1982","unstructured":"M. Jerrum and M. Snir, Some exact complexity results for straight-line computations over semirings, J. Assoc. Comput. Mach. 29 (1982), 874\u2013897.","journal-title":"J. Assoc. Comput. Mach."},{"key":"9231_CR16","unstructured":"P. W. Kasteleyn, Graph theory and crystal physics, in: Graph theory and theoretical physics, 43\u2013110, Academic Press, 1967."},{"key":"9231_CR17","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1002\/andp.18471481202","volume":"72","author":"G Kirchhoff","year":"1847","unstructured":"G. Kirchhoff, \u00dcber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchungen der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird, Ann. Phys. Chem. 72 (1847), 497\u2013508.","journal-title":"Ann. Phys. Chem."},{"key":"9231_CR18","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1137\/04061903X","volume":"29","author":"P Koev","year":"2007","unstructured":"P. Koev, Accurate computations with totally nonnegative matrices, SIAM J. Matrix Anal. Appl. 29 (2007), 731\u2013751.","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9231_CR19","doi-asserted-by":"crossref","first-page":"1483","DOI":"10.1016\/j.camwa.2012.09.008","volume":"65","author":"GL Litvinov","year":"2013","unstructured":"G. L. Litvinov, Idempotent and tropical mathematics; complexity of algorithms and interval analysis. Comput. Math. Appl. 65 (2013), 1483\u20131496.","journal-title":"Comput. Math. Appl."},{"key":"9231_CR20","unstructured":"I. G. Macdonald, Schur functions: theme and variations, S\u00e9minaire Lotharingien de Combinatoire (Saint-Nabor, 1992), 5\u201339, Publ. Inst. Rech. Math. Av., 498, Univ. Louis Pasteur, Strasbourg, 1992."},{"key":"9231_CR21","unstructured":"I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, 1999."},{"key":"9231_CR22","doi-asserted-by":"crossref","unstructured":"A. I. Molev, Comultiplication rules for the double Schur functions and Cauchy identities, Electron. J. Combin. 16 (2009), no. 1, Research Paper\u00a013, 44\u00a0pp.","DOI":"10.37236\/102"},{"key":"9231_CR23","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/s10801-006-0008-5","volume":"24","author":"H Narayanan","year":"2006","unstructured":"H. Narayanan, On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients, J. Algebraic Combin. 24, (2006), 347\u2013354.","journal-title":"J. Algebraic Combin."},{"key":"9231_CR24","unstructured":"G. P\u00f3lya, \u00dcber positive Darstellung von Polynomen, in: Vierteljschr. Naturforsch. Ges. Zrich 73 (1928), 141\u2013145; see: Collected Papers, vol. 2, MIT Press, Cambridge, 1974, pp. 309\u2013313."},{"key":"9231_CR25","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0022-4049(00)00155-9","volume":"164","author":"V Powers","year":"2001","unstructured":"V. Powers and B. Reznick, A new bound for P\u00f3lya\u2019s theorem with applications to polynomials positive on polyhedra, J. Pure Appl. Algebra 164 (2001), 221\u2013229.","journal-title":"J. Pure Appl. Algebra"},{"key":"9231_CR26","unstructured":"J. Riordan, Review MR0022160 (9,166f), Math. Reviews, AMS, 1948."},{"key":"9231_CR27","unstructured":"G. Rote, Division-free algorithms for the determinant and the Pfaffian: algebraic and combinatorial approaches. Computational discrete mathematics, 119\u2013135, Lecture Notes in Comput. Sci. 2122, Springer, Berlin, 2001."},{"key":"9231_CR28","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0304-3975(76)90083-9","volume":"2","author":"CP Schnorr","year":"1976","unstructured":"C. P. Schnorr, A lower bound on the number of additions in monotone computations, Theor. Comput. Sci. 2, (1976), 305\u2013315.","journal-title":"Theor. Comput. Sci."},{"key":"9231_CR29","unstructured":"E. Shamir and M. Snir, Lower bounds on the number of multiplications and the number of additions in monotone computations, Technical Report RC-6757, IBM, 1977."},{"key":"9231_CR30","unstructured":"A. Shpilka and A. Yehudayoff, Arithmetic circuits: a survey of recent results and open questions, Found. Trends Theor. Comput. Sci. 5 (2009), no. 3\u20134, 207\u2013388 (2010)."},{"key":"9231_CR31","doi-asserted-by":"crossref","unstructured":"R. P. Stanley, Enumerative combinatorics, vol. 2, Cambridge University Press, 1999.","DOI":"10.1017\/CBO9780511609589"},{"key":"9231_CR32","first-page":"184","volume":"264","author":"V Strassen","year":"1973","unstructured":"V. Strassen, Vermeidung von Divisionen, J. Reine Angew. Math. 264 (1973), 184\u2013202.","journal-title":"J. Reine Angew. Math."},{"key":"9231_CR33","unstructured":"W. T. Tutte, Graph theory, Addison-Wesley, 1984."},{"key":"9231_CR34","unstructured":"W. T. Tutte, Graph theory as I have known it, Oxford University Press, 1998."},{"key":"9231_CR35","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0304-3975(80)90060-2","volume":"12","author":"LG Valiant","year":"1980","unstructured":"L. G. Valiant, Negation can be exponentially powerful, Theor. Comput. Sci. 12, (1980), 303\u2013314.","journal-title":"Theor. Comput. Sci."},{"key":"9231_CR36","doi-asserted-by":"crossref","unstructured":"D. G. Wagner, Matroid inequalities from electrical network theory, Electron. J. Combin. 11 (2004\/06), no. 2, Article 1, 17 pp.","DOI":"10.37236\/1893"}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9231-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10208-014-9231-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-014-9231-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T18:07:09Z","timestamp":1747159629000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10208-014-9231-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,6]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9231"],"URL":"https:\/\/doi.org\/10.1007\/s10208-014-9231-y","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,6]]}}}