{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T05:00:09Z","timestamp":1725512409540},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540797081"},{"type":"electronic","value":"9783540797098"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-79709-8_12","type":"book-chapter","created":{"date-parts":[[2008,5,13]],"date-time":"2008-05-13T14:33:17Z","timestamp":1210689197000},"page":"86-98","source":"Crossref","is-referenced-by-count":4,"title":["Complexity of the Bollob\u00e1s-Riordan Polynomial"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[]},{"given":"Holger","family":"Dell","sequence":"additional","affiliation":[]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","unstructured":"Averbouch, I., Makowsky, J.A.: The complexity of multivariate matching polynomials (January 2007) (preprint)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1007\/978-3-540-73420-8_69","volume-title":"Automata, Languages and Programming","author":"M. Bl\u00e4ser","year":"2007","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 801\u2013812. Springer, Heidelberg (2007)"},{"key":"12_CR3","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. arXiv:0707.4565 (2007)"},{"key":"12_CR4","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":"12_CR5","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Heidelberg (1999)"},{"issue":"1-2","key":"12_CR6","doi-asserted-by":"publisher","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. Combinatorics, Probability and Computing\u00a08(1-2), 45\u201393 (1999)","journal-title":"Combinatorics, Probability and Computing"},{"key":"12_CR7","volume-title":"Grundlehren der mathematischen Wissenschaften","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. In: Grundlehren der mathematischen Wissenschaften, February 1997. Springer, Heidelberg (1997)"},{"key":"12_CR8","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":"12_CR9","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)"},{"issue":"1","key":"12_CR10","doi-asserted-by":"publisher","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. Mathematical Proceedings of the Cambridge Philosophical Society\u00a0108(1), 35\u201353 (1990)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"key":"12_CR11","doi-asserted-by":"publisher","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 Applied Mathematics\u00a025, 105\u2013127 (1989)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"12_CR12","doi-asserted-by":"publisher","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. Algebraic Discrete Methods\u00a07(2), 331\u2013335 (1986)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"12_CR13","doi-asserted-by":"publisher","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. Advances in Applied Mathematics\u00a032(1), 327\u2013349 (2004)","journal-title":"Advances in Applied Mathematics"},{"key":"12_CR14","doi-asserted-by":"publisher","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. Annals of Pure and Applied Logic\u00a0126, 1\u20133 (2004)","journal-title":"Annals of Pure and Applied Logic"},{"key":"12_CR15","unstructured":"Makowsky, J.A.: From a zoo to a zoology: Towards a general theory of graph polynomials. Theory of Computing Systems (2008), ISSN 1432-4350"},{"key":"12_CR16","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.\u00a0327, pp. 173\u2013226. Cambridge University Press, Cambridge (2005)"},{"issue":"10-11","key":"12_CR17","doi-asserted-by":"publisher","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 Mathematics\u00a0306(10-11), 905\u2013909 (2006)","journal-title":"Discrete Mathematics"},{"key":"12_CR18","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, London (1976)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-79709-8_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,18]],"date-time":"2023-05-18T09:31:19Z","timestamp":1684402279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-79709-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540797081","9783540797098"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-79709-8_12","relation":{},"subject":[]}}