{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:34:02Z","timestamp":1780382042917,"version":"3.54.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2009,5,15]],"date-time":"2009-05-15T00:00:00Z","timestamp":1242345600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00224-009-9213-7","type":"journal-article","created":{"date-parts":[[2009,5,14]],"date-time":"2009-05-14T18:26:12Z","timestamp":1242325572000},"page":"690-706","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of the Bollob\u00e1s\u2013Riordan Polynomial. Exceptional Points and Uniform Reductions"],"prefix":"10.1007","volume":"46","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Holger","family":"Dell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,5,15]]},"reference":[{"key":"9213_CR1","unstructured":"Averbouch, I., Makowsky, J.A.: The complexity of multivariate matching polynomials. Preprint (January 2007)"},{"key":"9213_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/978-3-540-92248-3_4","volume-title":"Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008. Revised Papers","author":"I. Averbouch","year":"2008","unstructured":"Averbouch, I., Godlin, B., Makowsky, J.A.: A most general edge elimination polynomial. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008. Revised Papers. Lecture Notes in Computer Science, vol. 5344, pp. 31\u201342. Springer, Berlin (2008)"},{"key":"9213_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (Philadelphia, Pennsylvania, USA, October 25\u201328, 2008), pp.\u00a0677\u2013686 (2008)","DOI":"10.1109\/FOCS.2008.40"},{"key":"9213_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1007\/978-3-540-73420-8_69","volume-title":"ICALP","author":"M. Bl\u00e4ser","year":"2007","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: Arge, L., Cachin, C., Jurdzinski, T., Tarlecki, A. (eds.) ICALP. Lecture Notes in Computer Science, vol. 4596, pp. 801\u2013812. Springer, Berlin (2007)"},{"key":"9213_CR5","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. 0707.4565 (2007)"},{"key":"9213_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0701-6","volume-title":"Complexity and Real Computation","author":"L. Blum","year":"1998","unstructured":"Blum, L., Cucker, F., Shub, M., Smale, S.: Complexity and Real Computation. Springer, New York (1998)"},{"key":"9213_CR7","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Berlin (1999)"},{"issue":"1\u20132","key":"9213_CR8","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1017\/S0963548398003447","volume":"8","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B., Riordan, O.: A Tutte polynomial for coloured graphs. Comb. Probab. Comput. 8(1\u20132), 45\u201393 (1999)","journal-title":"Comb. Probab. Comput."},{"key":"9213_CR9","series-title":"Grundlehren der mathematischen Wissenschaften","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der mathematischen Wissenschaften. Springer, Berlin (1997)"},{"key":"9213_CR10","doi-asserted-by":"crossref","unstructured":"Dell, H., Husfeldt, T., Wahl\u00e9n, M.: Exponential time complexity of the permanent and the Tutte polynomial. (2009, to appear)","DOI":"10.1007\/978-3-642-14165-2_37"},{"key":"9213_CR11","doi-asserted-by":"crossref","DOI":"10.1142\/5814","volume-title":"Chromatic Polynomials and Chromaticity of Graphs","author":"F.M. Dong","year":"2005","unstructured":"Dong, F.M., Koh, K.M., Teo, K.L.: Chromatic Polynomials and Chromaticity of Graphs. World Scientific, Singapore (2005)"},{"key":"9213_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/978-3-540-92248-3_17","volume-title":"Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008. Revised Papers","author":"B. Godlin","year":"2008","unstructured":"Godlin, B., Kotek, T., Makowsky, J.A.: Evaluations of graph polynomials. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30\u2013July 2, 2008. Revised Papers. Lecture Notes in Computer Science, vol. 5344, pp. 183\u2013194. Springer, Berlin (2008)"},{"key":"9213_CR13","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1145\/1250790.1250858","volume-title":"STOC","author":"L.A. Goldberg","year":"2007","unstructured":"Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. In: Johnson, D.S., Feige, U. (eds.) STOC, pp. 459\u2013468. ACM, New York (2007)"},{"key":"9213_CR14","unstructured":"Hoffmann, C.: A most general edge elimination polynomial\u2014thickening of edges. 0801.1600 (2008)"},{"issue":"1","key":"9213_CR15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Camb. Philos. Soc. 108(1), 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9213_CR16","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0166-218X(89)90049-8","volume":"25","author":"L.H. Kauffman","year":"1989","unstructured":"Kauffman, L.H.: A Tutte polynomial for signed graphs. Discrete Appl. Math. 25, 105\u2013127 (1989)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9213_CR17","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/0607036","volume":"7","author":"N. Linial","year":"1986","unstructured":"Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM J. Algebr. Discrete Methods 7(2), 331\u2013335 (1986)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"issue":"1","key":"9213_CR18","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/S0196-8858(03)00087-3","volume":"32","author":"M. Lotz","year":"2004","unstructured":"Lotz, M., Makowsky, J.A.: On the algebraic complexity of some families of coloured Tutte polynomials. Adv. Appl. Math. 32(1), 327\u2013349 (2004)","journal-title":"Adv. Appl. Math."},{"key":"9213_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"J.A. Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Ann. Pure Appl. Log. 126, 1\u20133 (2004)","journal-title":"Ann. Pure Appl. Log."},{"issue":"3","key":"9213_CR20","doi-asserted-by":"crossref","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"J.A. Makowsky","year":"2008","unstructured":"Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph polynomials. Theory Comput. Syst. 43(3), 542\u2013562 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9213_CR21","series-title":"London Mathematical Society Lecture Note Series","first-page":"173","volume-title":"Surveys in Combinatorics","author":"A.D. Sokal","year":"2005","unstructured":"Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Webb, B.S. (ed.) Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol. 327, pp.\u00a0173\u2013226. Cambridge University Press, Cambridge (2005)"},{"issue":"10\u201311","key":"9213_CR22","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1016\/j.disc.2006.03.010","volume":"306","author":"R.P. Stanley","year":"2006","unstructured":"Stanley, R.P.: Acyclic orientations of graphs. Discrete Math. 306(10\u201311), 905\u2013909 (2006)","journal-title":"Discrete Math."},{"issue":"2","key":"9213_CR23","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1137\/0220053","volume":"21","author":"S. Toda","year":"1991","unstructured":"Toda, S.: PP is as hard as the polynomial-time hierarchy. SIAM J.\u00a0Comput. 21(2), 865\u2013877 (1991)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9213_CR24","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(92)90369-Q","volume":"100","author":"S. Toda","year":"1992","unstructured":"Toda, S., Watanabe, O.: Polynomial time 1-Turing reductions from #PH to #P. Theor. Comput. Sci. 100, 205\u2013221 (1992)","journal-title":"Theor. Comput. Sci."},{"key":"9213_CR25","series-title":"London Mathematical Society Monographs","volume-title":"Matroid Theory","author":"D.J.A. Welsh","year":"1976","unstructured":"Welsh, D.J.A.: Matroid Theory. London Mathematical Society Monographs, vol.\u00a08. Academic Press, San Diego (1976)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9213-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-009-9213-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9213-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,25]],"date-time":"2023-05-25T04:20:12Z","timestamp":1684988412000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9213-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5,15]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["9213"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9213-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,5,15]]}}}