{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T03:59:36Z","timestamp":1754107176214},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540483816"},{"type":"electronic","value":"9783540483823"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11917496_18","type":"book-chapter","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T02:16:13Z","timestamp":1161137773000},"page":"191-204","source":"Crossref","is-referenced-by-count":17,"title":["Computing Graph Polynomials on Graphs of Bounded Clique-Width"],"prefix":"10.1007","author":[{"given":"J. A.","family":"Makowsky","sequence":"first","affiliation":[]},{"given":"Udi","family":"Rotics","sequence":"additional","affiliation":[]},{"given":"Ilya","family":"Averbouch","sequence":"additional","affiliation":[]},{"given":"Benny","family":"Godlin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"18_CR1","unstructured":"Arratia, R., Bollobas, B., Sorkin, G.B.: The interlace polynomial: a new graph polynomial. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Mathematics, pp. 237\u2013245 (2000)"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.jctb.2004.03.003","volume":"92","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollobas, B., Sorkin, G.B.: The interlace polynomial: a new graph polynomial. Journal of Combinatorial Theory, Series B\u00a092, 199\u2013233 (2004)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"18_CR3","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s00493-004-0035-6","volume":"24","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollobas, B., Sorkin, G.B.: A two-variable interlace polynomial. Combinatorica\u00a024(4), 567\u2013584 (2004)","journal-title":"Combinatorica"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embedding in a k\u2013tree. SIAM. J. Algebraic Discrete Methods\u00a08, 277\u2013284 (1987)","journal-title":"SIAM. J. Algebraic Discrete Methods"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"A. Andrzejak","year":"1998","unstructured":"Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Mathematics\u00a0190, 39\u201354 (1998)","journal-title":"Discrete Mathematics"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.laa.2003.06.010","volume":"377","author":"M. Aigner","year":"2004","unstructured":"Aigner, M., van der Holst, H.: Interlace polynomials. Linear Algebra and Applications\u00a0377, 11\u201330 (2004)","journal-title":"Linear Algebra and Applications"},{"key":"18_CR7","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":"18_CR8","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(86)90014-4","volume":"15","author":"D. Babi\u0107","year":"1986","unstructured":"Babi\u0107, D., Graovac, A., Mohar, B., Pisanski, T.: The matching polynomial of a polygraph. Discrete Applied Mathematics\u00a015, 11\u201324 (1986)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR9","volume-title":"Algebraic Graph Theory","author":"N. Biggs","year":"1993","unstructured":"Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)","edition":"2"},{"key":"18_CR10","doi-asserted-by":"publisher","first-page":"42","DOI":"10.2307\/1967597","volume":"14","author":"G.D. Birkhoff","year":"1912","unstructured":"Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Annals of Mathematics\u00a014, 42\u201346 (1912)","journal-title":"Annals of Mathematics"},{"key":"18_CR11","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1999","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Springer, Heidelberg (1999)"},{"key":"18_CR12","unstructured":"Cvetkovi\u0107, D.M., Doob, M., Sachs, H.: Spectra of graphs, Johann Ambrosius Barth, 3rd edn. (1995)"},{"key":"18_CR13","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. System Sci.\u00a046, 218\u2013270 (1993)","journal-title":"J. Comput. System Sci."},{"issue":"1-2","key":"18_CR14","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"},{"key":"18_CR15","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\u2013width of graphs. Discrete Applied Mathematics\u00a0101, 77\u2013114 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Courcelle, B., Oum, S.: Vertex-minors, monadic second-order logic, and a conjecture by Seese. Journal of Combinatorial Theory, Series B, xx:xx\u2013xx (2006)","DOI":"10.1016\/j.jctb.2006.04.003"},{"issue":"4","key":"18_CR17","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"D.G. Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput.\u00a034(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"key":"18_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.F.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"18_CR19","volume-title":"Graduate Texts in Mathematics","author":"R. Diestel","year":"1996","unstructured":"Diestel, R.: Graph Theory. In: Graduate Texts in Mathematics. Springer, Heidelberg (1996)"},{"key":"18_CR20","doi-asserted-by":"publisher","DOI":"10.1142\/9789812569462","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":"18_CR21","first-page":"33","volume":"1","author":"M. F\u00fcrer","year":"2003","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. Electronic Colloquium on Computational Complexity\u00a01, R33 (2003)","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"18_CR22","unstructured":"Fischer, E., Makowsky, J.A., Ravve, E.V.: Counting truth assignments of formulas of bounded tree width and clique-width. Discrete Applied Mathematics, xx:xx\u2013xx (2006)"},{"key":"18_CR23","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Proving NP-hardness for clique width. In: ECCC, xx:xx\u2013yy (2005)"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/11604686_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"O. Gim\u00e9nez","year":"2005","unstructured":"Gim\u00e9nez, O., Hlin\u011bn\u00fd, P., Noy, M.: Computing the Tutte polynomial on graphs of bounded clique-width. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 59\u201368. Springer, Heidelberg (2005)"},{"key":"18_CR25","doi-asserted-by":"crossref","unstructured":"Gim\u00e9nez, O., Hlin\u0115n\u00fd, P., Noy, M.: Computing the Tutte polynomial on graphs of bounded clique-width. XXX, xx:xx\u2013yy (2006)","DOI":"10.1007\/11604686_6"},{"key":"18_CR26","volume-title":"Graduate Texts in Mathematics","author":"C. Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory. In: Graduate Texts in Mathematics. Springer, Heidelberg (2001)"},{"key":"18_CR27","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. Phil. Soc.\u00a0108, 35\u201353 (1990)","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"18_CR28","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0166-218X(02)00198-1","volume":"126","author":"D. Kobler","year":"2003","unstructured":"Kobler, D., Rotics, U.: Edge dominating set and colorings on graphs with fixed clique-width. Discrete Applied Mathematics\u00a0126, 197\u2013221 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"18_CR29","volume-title":"Matching Theory","author":"L. Lovasz","year":"1986","unstructured":"Lovasz, L., Plummer, M.: Matching Theory. North-Holland, Amsterdam (1986)"},{"key":"18_CR30","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":"18_CR31","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"S.D. Noble","year":"1998","unstructured":"Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinatorics, Probability and Computing\u00a07, 307\u2013321 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Ser. B, xx(x):xx\u2013yy (2005)","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"18_CR33","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0012-365X(92)90289-R","volume":"109","author":"J.G. Oxley","year":"1992","unstructured":"Oxley, J.G., Welsh, D.J.A.: Tutte polynomials computable in polynomial time. Discrete Mathematics\u00a0109, 185\u2013192 (1992)","journal-title":"Discrete Mathematics"},{"key":"18_CR34","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"18_CR35","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(73)90108-8","volume":"5","author":"R.P. Stanley","year":"1973","unstructured":"Stanley, R.P.: Acyclic orientations of graphs. Discrete Mathematics\u00a05, 171\u2013178 (1973)","journal-title":"Discrete Mathematics"},{"key":"18_CR36","volume-title":"Chemical graph theory","author":"N. Trinajsti\u0107","year":"1992","unstructured":"Trinajsti\u0107, N.: Chemical graph theory, 2nd edn. CRC Press, Boca Raton (1992)","edition":"2"},{"issue":"3","key":"18_CR37","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR38","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1017\/S0963548300000195","volume":"1","author":"D.L. Vertigan","year":"1992","unstructured":"Vertigan, D.L., Welsh, D.J.A.: The computational complexity of the Tutte plane: The bipartite case. Combinatorics, Probability, and Computing\u00a01, 181\u2013187 (1992)","journal-title":"Combinatorics, Probability, and Computing"},{"key":"18_CR39","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: Knots, Colourings and Counting","author":"D.J.A. Welsh","year":"1993","unstructured":"Welsh, D.J.A.: Complexity: Knots, Colourings and Counting. London Mathematical Society Lecture Notes Series, vol.\u00a0186. Cambridge University Press, Cambridge (1993)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11917496_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T14:58:31Z","timestamp":1605625111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11917496_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540483816","9783540483823"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/11917496_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}