{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:33:36Z","timestamp":1780382016687,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642229923","type":"print"},{"value":"9783642229930","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_12","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T08:44:46Z","timestamp":1312879486000},"page":"96-107","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree"],"prefix":"10.1007","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Radu","family":"Curticapean","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-92248-3_4","volume-title":"Graph-Theoretic Concepts in Computer Science","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.) WG 2008. LNCS, vol.\u00a05344, pp. 31\u201342. Springer, Heidelberg (2008)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Computing the Tutte polynomial in vertex-exponential time. In: FOCS 2008, pp. 677\u2013686 (2008)","DOI":"10.1109\/FOCS.2008.40"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Dell, H.: Complexity of the cover polynomial. In: ICALP, pp. 801\u2013812 (2007)","DOI":"10.1007\/978-3-540-73420-8_69"},{"key":"12_CR4","unstructured":"Bl\u00e4ser, M., Dell, H., Fouz, M.: Complexity and approximability of the cover polynomial. Computation Complexity (accepted)"},{"key":"12_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/978-3-540-79709-8_12","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser, M., Dell, H., Makowsky, J.A.: Complexity of the bollob\u00e1s-riordan polynomial. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science \u2013 Theory and Applications. LNCS, vol.\u00a05010, pp. 86\u201398. Springer, Heidelberg (2008)"},{"key":"12_CR6","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl, Germany, pp. 97\u2013108 (2008)"},{"issue":"1-2","key":"12_CR7","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_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J.-y., Lu, P., Xia, M.: Holographic algorithms with matchgates capture precisely tractable planar #CSP. CoRR abs\/1008.0683 (2010)","DOI":"10.1109\/FOCS.2010.48"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1006\/jctb.1995.1055","volume":"65","author":"F.R.K. Chung","year":"1995","unstructured":"Chung, F.R.K., Graham, R.L.: On the cover polynomial of a digraph. J. Combin. Theory Ser. B\u00a065, 273\u2013290 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1-2","key":"12_CR10","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"12_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/aama.2000.0689","volume":"25","author":"O.M. D\u2019Antona","year":"2000","unstructured":"D\u2019Antona, O.M., Munarini, E.: The cycle-path indicator polynomial of a digraph. Advances in Applied Mathematics\u00a025(1), 41\u201356 (2000)","journal-title":"Advances in Applied Mathematics"},{"issue":"7","key":"12_CR12","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.ic.2008.04.003","volume":"206","author":"L.A. Goldberg","year":"2008","unstructured":"Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial. Inform. Comput.\u00a0206(7), 908\u2013929 (2008)","journal-title":"Inform. Comput."},{"key":"12_CR13","unstructured":"Goldberg, L.A., Jerrum, M.: Inapproximability of the Tutte polynomial of a planar graph. CoRR abs\/0907.1724 (2009)"},{"issue":"4","key":"12_CR14","doi-asserted-by":"crossref","first-page":"373","DOI":"10.3233\/FI-2010-233","volume":"98","author":"C. Hoffmann","year":"2010","unstructured":"Hoffmann, C.: A most general edge elimination polynomial - thickening of edges. Fundam. Inform.\u00a098(4), 373\u2013378 (2010)","journal-title":"Fundam. Inform."},{"issue":"1","key":"12_CR15","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. Math. Proc. of the Cambridge Phil. Society\u00a0108(1), 35\u201353 (1990)","journal-title":"Math. Proc. of the Cambridge Phil. Society"},{"issue":"2","key":"12_CR16","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_CR17","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"},{"issue":"3","key":"12_CR18","doi-asserted-by":"publisher","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 of Computing Systems\u00a043(3), 542\u2013562 (2008)","journal-title":"Theory of Computing Systems"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/FOCS.2004.34","volume-title":"FOCS 2004: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2004","unstructured":"Valiant, L.G.: Holographic algorithms (extended abstract). In: FOCS 2004: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 306\u2013315. IEEE Computer Society, Washington, DC (2004)"},{"issue":"3","key":"12_CR20","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1137\/S0097539704446797","volume":"35","author":"D.L. Vertigan","year":"2005","unstructured":"Vertigan, D.L.: The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput.\u00a035(3), 690\u2013712 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"12_CR21","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M. Xia","year":"2007","unstructured":"Xia, M., Zhang, P., Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theoretical Computer Science\u00a0384(1), 111\u2013125 (2007)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T22:10:10Z","timestamp":1606169410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}