{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T22:05:16Z","timestamp":1779919516330,"version":"3.53.1"},"publisher-location":"Cham","reference-count":15,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031863189","type":"print"},{"value":"9783031863196","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-86319-6_10","type":"book-chapter","created":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T03:00:53Z","timestamp":1754362853000},"page":"111-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the Counting Complexity of the Cover Polynomial for Simple Graphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1750-9036","authenticated-orcid":false,"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-4403-9380","authenticated-orcid":false,"given":"Nico","family":"Mansion","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,8]]},"reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ejc.2009.05.006","volume":"31","author":"I Averbouch","year":"2010","unstructured":"Averbouch, I., Godlin, B., Makowsky, J.A.: An extension of the bivariate chromatic polynomial. Eur. J. Comb. 31(1), 1\u201317 (2010)","journal-title":"Eur. J. Comb."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-642-22993-0_12","volume-title":"Mathematical Foundations of Computer Science 2011","author":"M Bl\u00e4ser","year":"2011","unstructured":"Bl\u00e4ser, M., Curticapean, R.: The complexity of the cover polynomials for planar graphs of bounded degree. In: Murlak, F., Sankowski, P. (eds.) Mathematical Foundations of Computer Science 2011, pp. 96\u2013107. Springer Berlin Heidelberg, Berlin\/Heidelberg (2011)"},{"key":"10_CR3","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.) Automata, Languages and Programming, pp. 801\u2013812. Springer Berlin Heidelberg, Berlin\/Heidelberg (2007)"},{"key":"10_CR4","first-page":"97","volume-title":"STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21\u201323, 2008, Proceedings. LIPIcs","author":"M Bl\u00e4ser","year":"2008","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: Albers S., Weil, P. (eds.) STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21-23, 2008, Proceedings. LIPIcs, vol. 1, pp. 97\u2013108. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Germany (2008)"},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00224-009-9213-7","volume":"46","author":"M Bl\u00e4ser","year":"2010","unstructured":"Bl\u00e4ser, M., Dell, H., Makowsky, J.A.: Complexity of the Bollob\u00e1s-Riordan polynomial. Exceptional points and uniform reductions. Theory Comput. Syst. 46(4), 690\u2013706 (2010)","journal-title":"Exceptional points and uniform reductions. Theory Comput. Syst."},{"issue":"3","key":"10_CR6","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00037-011-0018-0","volume":"21","author":"M Bl\u00e4ser","year":"2012","unstructured":"Bl\u00e4ser, M., Dell, H., Fouz, M.: Complexity and approximability of the cover polynomial. Comput. Complex. 21(3), 359\u2013419 (2012)","journal-title":"Comput. Complex."},{"issue":"2","key":"10_CR7","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1006\/jctb.1995.1055","volume":"65","author":"FRK Chung","year":"1995","unstructured":"Chung, F.R.K., Graham, R.L.: On the cover polynomial of a digraph. J. Comb. Theory Series B 65(2), 273\u2013290 (1995)","journal-title":"J. Comb. Theory Series B"},{"key":"10_CR8","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.jctb.2017.04.003","volume":"126","author":"F Chung","year":"2017","unstructured":"Chung, F., Graham, R.: The drop polynomial of a weighted digraph. J. Comb. Theory Series B 126, 62\u201382 (2017)","journal-title":"J. Comb. Theory Series B"},{"issue":"1","key":"10_CR9","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/aama.2000.0689","volume":"25","author":"OM D\u2019Antona","year":"2000","unstructured":"D\u2019Antona, O.M., Munarini, E.: The cycle-path indicator polynomial of a digraph. Adv. Appl. Math. 25(1), 41\u201356 (2000)","journal-title":"Adv. Appl. Math."},{"key":"10_CR10","volume-title":"Handbook of the Tutte Polynomial and Related Topics","year":"2022","unstructured":"Ellis-Monaghan, J.A., Moffatt, I. (eds.): Handbook of the Tutte Polynomial and Related Topics, 1st edn. Chapman and Hall\/CRC, Boca Raton (2022)","edition":"1"},{"key":"10_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.aam.2017.04.005","volume":"94","author":"AJ Goodall","year":"2018","unstructured":"Goodall, A.J., Hermann, M., Kotek, T., Makowsky, J.A., Noble, S.D.: On the complexity of generalized chromatic polynomials. Adv. Appl. Math. 94, 71\u2013102 (2018)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"10_CR12","doi-asserted-by":"publisher","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 \u2013 Thickening of edges. Fundam. Informaticae 98(4), 373\u2013378 (2010)","journal-title":"Fundam. Informaticae"},{"key":"10_CR13","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. Camb. Philos. Soc. 108, 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"issue":"1\u20133","key":"10_CR14","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0304-3975(03)00080-X","volume":"304","author":"M Liskiewicz","year":"2003","unstructured":"Liskiewicz, M., Ogihara, M., Toda, S.: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theor. Comput. Sci. 304(1\u20133), 129\u2013156 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3\u20134","key":"10_CR15","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"JA 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\u20134), 542\u2013562 (2008)","journal-title":"Theory Comput. Syst."}],"container-title":["Trends in Mathematics","Model Theory, Computer Science, and Graph Polynomials"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-86319-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T21:28:20Z","timestamp":1779917300000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-86319-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031863189","9783031863196"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-86319-6_10","relation":{},"ISSN":["2297-0215","2297-024X"],"issn-type":[{"value":"2297-0215","type":"print"},{"value":"2297-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"8 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}