{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T06:32:05Z","timestamp":1743143525963,"version":"3.40.3"},"publisher-location":"Cham","reference-count":40,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286778"},{"type":"electronic","value":"9783319286785"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-28678-5_10","type":"book-chapter","created":{"date-parts":[[2016,1,8]],"date-time":"2016-01-08T15:14:18Z","timestamp":1452266058000},"page":"135-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Computation of Generalized Ising Polynomials on Graphs with Fixed Clique-Width"],"prefix":"10.1007","author":[{"given":"Tomer","family":"Kotek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johann A.","family":"Makowsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,9]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1090\/conm\/531\/10460","volume":"531","author":"S Akbari","year":"2010","unstructured":"Akbari, S., Alikhani, S., Oboudi, M.R., Peng, Y.-H.: On the zeros of domination polynomial of a graph. Comb. Graphs 531, 109\u2013115 (2010)","journal-title":"Comb. Graphs"},{"issue":"7","key":"10_CR2","doi-asserted-by":"publisher","first-page":"1714","DOI":"10.1016\/j.ejc.2010.03.007","volume":"31","author":"S Akbari","year":"2010","unstructured":"Akbari, S., Alikhani, S., Peng, Y.: Characterization of graphs using domination polynomials. Eur. J. Comb. 31(7), 1714\u20131724 (2010)","journal-title":"Eur. J. Comb."},{"key":"10_CR3","first-page":"353","volume":"116","author":"S Akbari","year":"2014","unstructured":"Akbari, S., Oboudi, M.R.: Cycles are determined by their domination polynomials. Ars Comb. 116, 353\u2013358 (2014)","journal-title":"Ars Comb."},{"issue":"1","key":"10_CR4","first-page":"143","volume":"6","author":"M Alaeiyan","year":"2011","unstructured":"Alaeiyan, M., Bahrami, A., Farahani, M.R.: Cyclically domination polynomial of molecular graph of some nanotubes. Digest J. Nanomaterials Biostructures 6(1), 143\u2013147 (2011)","journal-title":"Digest J. Nanomaterials Biostructures"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1155\/2009\/542040","volume":"2009","author":"S Alikhani","year":"2009","unstructured":"Alikhani, S., Peng, Y.-H.: Dominating sets and domination polynomials of paths. Int. J. Math. Math. Sci. 2009, 10 (2009)","journal-title":"Int. J. Math. Math. Sci."},{"key":"10_CR6","first-page":"257","volume":"114","author":"S Alikhani","year":"2014","unstructured":"Alikhani, S., Peng, Y.: Introduction to domination polynomial of a graph. Ars Comb. 114, 257\u2013266 (2014)","journal-title":"Ars Comb."},{"issue":"11","key":"10_CR7","doi-asserted-by":"publisher","first-page":"2515","DOI":"10.1016\/j.dam.2009.02.021","volume":"157","author":"D Andr\u00e9n","year":"2009","unstructured":"Andr\u00e9n, D., Markstr\u00f6m, K.: The bivariate ising polynomial of a graph. Discrete Appl. Math. 157(11), 2515\u20132524 (2009)","journal-title":"Discrete Appl. Math."},{"key":"10_CR8","first-page":"39","volume":"190","author":"A Andrzejak","year":"1998","unstructured":"Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. DMATH: Discrete Math. 190, 39\u201354 (1998)","journal-title":"DMATH: Discrete Math."},{"issue":"2","key":"10_CR9","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991)","journal-title":"J. Algorithms"},{"issue":"1","key":"10_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.7151\/dmgt.1106","volume":"20","author":"JL Arocha","year":"2000","unstructured":"Arocha, J.L., Llano, B.: Mean value for the matching and dominating polynomial. Discussiones Math. Graph Theor. 20(1), 57\u201369 (2000)","journal-title":"Discussiones Math. Graph Theor."},{"key":"10_CR11","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: STACS 2008, pp. 97\u2013108. IBFI Schloss Dagstuhl (2008)"},{"issue":"3","key":"10_CR12","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s00373-013-1306-z","volume":"30","author":"JI Brown","year":"2014","unstructured":"Brown, J.I., Tufts, J.: On the roots of domination polynomials. Graphs Comb. 30(3), 527\u2013547 (2014)","journal-title":"Graphs Comb."},{"issue":"1","key":"10_CR13","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inform. Comput. 85(1), 12\u201375 (1990)","journal-title":"Inform. Comput."},{"key":"10_CR14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach, vol. 138. Cambridge University Press, Cambridge (2012)"},{"issue":"2","key":"10_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125\u2013150 (2000)","journal-title":"Theor. Comput. Syst."},{"issue":"1","key":"10_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101(1), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.7151\/dmgt.1808","volume":"35","author":"M Dod","year":"2015","unstructured":"Dod, M., Kotek, T., Preen, J., Tittmann, P.: Bipartition polynomials, the ising model and domination in graphs. Discussiones Math. Graph Theor. 35(2), 335\u2013353 (2015)","journal-title":"Discussiones Math. Graph Theor."},{"key":"10_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity, vol. 3. springer, Heidelberg (1999)"},{"key":"10_CR19","volume-title":"Finite Model Theory","author":"H-D Ebbinghaus","year":"2005","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Springer Science & Business Media, Heidelberg (2005)"},{"key":"10_CR20","series-title":"Texts in Theoretical Computer Science. An EATCS Series","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, vol. 14. Springer, Heidelberg (2006)"},{"key":"10_CR21","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Algorithmic lower bounds for problems parameterized with clique-width. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17\u201319, 2010, pp. 493\u2013502 (2010)"},{"issue":"4","key":"10_CR22","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/050645208","volume":"20","author":"O Gim\u00e9nez","year":"2006","unstructured":"Gim\u00e9nez, O., Hlinen\u1ef3, P., Noy, M.: Computing the Tutte polynomial on graphs of bounded clique-width. SIAM J. Discrete Math. 20(4), 932\u2013946 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"10_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-540-92248-3_17","volume-title":"Graph-Theoretic Concepts in Computer Science","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.) WG 2008. LNCS, vol. 5344, pp. 183\u2013194. Springer, Heidelberg (2008)"},{"issue":"2","key":"10_CR24","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1002\/rsa.10090","volume":"23","author":"LA Goldberg","year":"2003","unstructured":"Goldberg, L.A., Jerrum, M., Paterson, M.: The computational complexity of two-state spin systems. Random Struct. Algorithms 23(2), 133\u2013154 (2003)","journal-title":"Random Struct. Algorithms"},{"issue":"01","key":"10_CR25","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. Cambridge Philos. Soc. 108(01), 35\u201353 (1990)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"key":"10_CR26","unstructured":"Kahat, S.S., Khalaf, A.J.M., Roslan, R.: Dominating sets and domination polynomial of wheels. Asian J. Appl. Sci. 2(3) (2014)"},{"issue":"05","key":"10_CR27","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1017\/S0963548312000259","volume":"21","author":"T Kotek","year":"2012","unstructured":"Kotek, T.: Complexity of ising polynomials. Comb. Prob. Comput. 21(05), 743\u2013772 (2012)","journal-title":"Comb. Prob. Comput."},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Kotek, T., Makowsky, J.A.: Connection matrices and the definability of graph parameters. Logical Methods in Computer Science, 10(4) (2014)","DOI":"10.2168\/LMCS-10(4:1)2014"},{"issue":"3","key":"10_CR29","doi-asserted-by":"crossref","first-page":"P47","DOI":"10.37236\/2475","volume":"19","author":"T Kotek","year":"2012","unstructured":"Kotek, T., Preen, J., Simon, F., Tittmann, P., Trinks, M.: Recurrence relations and splitting formulas for the domination polynomial. Electr. J. Comb. 19(3), P47 (2012)","journal-title":"Electr. J. Comb."},{"key":"10_CR30","unstructured":"Kotek, T., Preen, J., Tittmann, P.: Domination polynomials of graph products. To appear in Journal of Combinatorial Mathematics and Combinatorial Computing"},{"issue":"3","key":"10_CR31","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s00373-013-1286-z","volume":"30","author":"T Kotek","year":"2014","unstructured":"Kotek, T., Preen, J., Tittmann, P.: Subset-sum representations of domination polynomials. Graphs Comb. 30(3), 647\u2013660 (2014)","journal-title":"Graphs Comb."},{"key":"10_CR32","unstructured":"Levit, V.E., Mandrescu, E.: The independence polynomial of a graph-a survey. In: Proceedings of the 1st International Conference on Algebraic Informatics, pp. 233\u2013254 (2005)"},{"issue":"1","key":"10_CR33","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.apal.2003.11.002","volume":"126","author":"JA Makowsky","year":"2004","unstructured":"Makowsky, J.A.: Algorithmic uses of the Feferman-Vaught theorem. Ann. Pure Appl. Logic 126(1), 159\u2013213 (2004)","journal-title":"Ann. Pure Appl. Logic"},{"issue":"2","key":"10_CR34","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1016\/j.dam.2004.01.016","volume":"145","author":"JA Makowsky","year":"2005","unstructured":"Makowsky, J.A.: Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl. Math. 145(2), 276\u2013290 (2005)","journal-title":"Discrete Appl. Math."},{"key":"10_CR35","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-540-92701-3_4","volume-title":"Logic and Its Applications","author":"JA Makowsky","year":"2009","unstructured":"Makowsky, J.A.: Connection matrices for MSOL-definable structural invariants. In: Ramanujam, R., Sarukkai, S. (eds.) Logic and Its Applications. LNCS (LNAI), vol. 5378, pp. 51\u201364. Springer, Heidelberg (2009)"},{"key":"10_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/11917496_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Johann A Makowsky","year":"2006","unstructured":"Makowsky, Johann A., Rotics, Udi, Averbouch, Ilya, Godlin, Benny: Computing graph polynomials on graphs of bounded clique-width. In: Fomin, Fedor V. (ed.) WG 2006. LNCS, vol. 4271, pp. 191\u2013204. Springer, Heidelberg (2006)"},{"key":"10_CR37","doi-asserted-by":"crossref","unstructured":"Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. In: Combinatorics, Probability and Computing, vol. 7, Cambridge University Press (1998)","DOI":"10.1017\/S0963548398003551"},{"key":"10_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11604686_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S Oum","year":"2005","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 49\u201358. Springer, Heidelberg (2005)"},{"key":"10_CR39","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S-I Oum","year":"2006","unstructured":"Oum, S.-I., Seymour, P.: Approximating clique-width and branch-width. J. Comb. Theor. Ser. B 96, 514\u2013528 (2006)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"3","key":"10_CR40","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Topics in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28678-5_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,13]],"date-time":"2020-09-13T19:13:39Z","timestamp":1600024419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28678-5_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319286778","9783319286785"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28678-5_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 January 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}