{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T21:19:10Z","timestamp":1694639950183},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,8,6]],"date-time":"2010-08-06T00:00:00Z","timestamp":1281052800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,9]]},"DOI":"10.1007\/s00453-010-9439-4","type":"journal-article","created":{"date-parts":[[2010,8,5]],"date-time":"2010-08-05T14:18:21Z","timestamp":1281017901000},"page":"3-35","source":"Crossref","is-referenced-by-count":4,"title":["Fast Evaluation of Interlace Polynomials on Graphs of\u00a0Bounded Treewidth"],"prefix":"10.1007","volume":"61","author":[{"given":"Markus","family":"Bl\u00e4ser","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Hoffmann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,8,6]]},"reference":[{"key":"9439_CR1","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.laa.2003.06.010","volume":"377","author":"M. Aigner","year":"2004","unstructured":"Aigner, M., van\u00a0der Holst, H.: Interlace polynomials. Linear Algebra Appl. 377, 11\u201330 (2004)","journal-title":"Linear Algebra Appl."},{"issue":"1\u20133","key":"9439_CR2","doi-asserted-by":"crossref","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 Math. 190(1\u20133), 39\u201354 (1998)","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"9439_CR3","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0166-218X(00)00190-6","volume":"104","author":"R. Arratia","year":"2000","unstructured":"Arratia, R., Bollob\u00e1s, B., Coppersmith, D., Sorkin, G.B.: Euler circuits and DNA sequencing by hybridization. Discrete Appl. Math. 104(1\u20133), 63\u201396 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"9439_CR4","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/j.jctb.2004.03.003","volume":"92","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: The interlace polynomial of a graph. J. Comb. Theory Ser. B 92(2), 199\u2013233 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"9439_CR5","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1007\/s00493-004-0035-6","volume":"24","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: A two-variable interlace polynomial. Combinatorica 24(4), 567\u2013584 (2004)","journal-title":"Combinatorica"},{"key":"9439_CR6","doi-asserted-by":"crossref","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. Lecture Notes in Computer Science, vol.\u00a05344, pp. 31\u201342 (2008)","DOI":"10.1007\/978-3-540-92248-3_4"},{"key":"9439_CR7","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), pp.\u00a097\u2013108, Dagstuhl, Germany, 2008. Internationales Begegnungs- und Forschungszentrum f\u00fcr Informatik (IBFI), Schloss Dagstuhl, Germany"},{"issue":"6","key":"9439_CR8","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J.\u00a0Comput. 25(6), 1305\u20131317 (1996)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"1\u20132","key":"9439_CR9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9439_CR10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008)","journal-title":"Comput. J."},{"issue":"2","key":"9439_CR11","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1006\/jctb.2001.2102","volume":"85","author":"B. Bollob\u00e1s","year":"2002","unstructured":"Bollob\u00e1s, B.: Evaluations of the circuit partition polynomial. J. Comb. Theory Ser. B 85(2), 261\u2013268 (2002)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1\u20132","key":"9439_CR12","doi-asserted-by":"crossref","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. Comb. Probab. Comput. 8(1\u20132), 45\u201393 (1999)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"9439_CR13","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0195-6698(87)80027-6","volume":"8","author":"A. Bouchet","year":"1987","unstructured":"Bouchet, A.: Isotropic systems. Eur. J. Comb. 8(3), 231\u2013244 (1987)","journal-title":"Eur. J. Comb."},{"issue":"1","key":"9439_CR14","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/0095-8956(88)90055-X","volume":"45","author":"A. Bouchet","year":"1988","unstructured":"Bouchet, A.: Graphic presentations of isotropic systems. J. Comb. Theory Ser. B 45(1), 58\u201376 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9439_CR15","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF01787630","volume":"7","author":"A. Bouchet","year":"1991","unstructured":"Bouchet, A.: Tutte Martin polynomials and orienting vectors of isotropic systems. Graphs Comb. 7, 235\u2013252 (1991)","journal-title":"Graphs Comb."},{"issue":"13","key":"9439_CR16","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.disc.2004.07.028","volume":"302","author":"A. Bouchet","year":"2005","unstructured":"Bouchet, A.: Graph polynomials derived from Tutte\u2013Martin polynomials. Discrete Math. 302(13), 32\u201338 (2005)","journal-title":"Discrete Math."},{"key":"9439_CR17","series-title":"Grundlehren der Mathematischen Wissenschaften\/A Series of Comprehensive Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic Complexity Theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic Complexity Theory. Grundlehren der Mathematischen Wissenschaften\/A Series of Comprehensive Studies in Mathematics, vol.\u00a0315. Springer, Berlin (1997)"},{"key":"9439_CR18","unstructured":"B\u00e9nard, D., Bouchet, A., Duchamp, A.: On the Martin and Tutte polynomials. Technical report, D\u00e9partement d\u2019Infornmatique, Universit\u00e9 du Maine, Le Mans, France (1997)"},{"key":"9439_CR19","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: A multivariate interlace polynomial and its computation for graphs of bounded clique-width. Electron. J.\u00a0Comb. 15(1) (2008)","DOI":"10.37236\/793"},{"issue":"1\u20133","key":"9439_CR20","doi-asserted-by":"crossref","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\u20133), 77\u2013114 (2000)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9439_CR21","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jctb.2006.04.003","volume":"97","author":"B. Courcelle","year":"2007","unstructured":"Courcelle, B., Oum, S.-i.: Vertex-minors, monadic second-order logic, and a conjecture by seese. J.\u00a0Comb. Theory, Ser. B 97(1), 91\u2013126 (2007)","journal-title":"J.\u00a0Comb. Theory, Ser. B"},{"issue":"1\u20132","key":"9439_CR22","doi-asserted-by":"crossref","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 Appl. Math. 108(1\u20132), 23\u201352 (2001)","journal-title":"Discrete Appl. Math."},{"key":"9439_CR23","unstructured":"Danielsen, L.E., Parker, M.G.: Interlace polynomials: Enumeration, unimodality, and connections to codes. Preprint (2008). arXiv:0804.2576v1"},{"key":"9439_CR24","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"issue":"2","key":"9439_CR25","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1006\/jctb.1998.1853","volume":"74","author":"J.A. Ellis-Monaghan","year":"1998","unstructured":"Ellis-Monaghan, J.A.: New results for the Martin polynomial. J. Comb. Theory Ser. B 74(2), 326\u2013352 (1998)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9439_CR26","unstructured":"Ellis-Monaghan, J.A.: Martin polynomial miscellanea. In: Proceedings of the 30th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, pp.\u00a019\u201331, Boca Raton, FL, 1999"},{"key":"9439_CR27","unstructured":"Ellis-Monaghan, J.A., Sarmiento, I.: Isotropic systems and the interlace polynomial. Preprint (2006). arXiv:math\/0606641v2"},{"issue":"6","key":"9439_CR28","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1017\/S0963548307008723","volume":"16","author":"J.A. Ellis-Monaghan","year":"2007","unstructured":"Ellis-Monaghan, J.A., Sarmiento, I.: Distance hereditary graphs and the interlace polynomial. Comb. Probab. Comput. 16(6), 947\u2013973 (2007)","journal-title":"Comb. Probab. Comput."},{"issue":"5","key":"9439_CR29","doi-asserted-by":"crossref","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM J.\u00a0Comput. 39(5), 1941\u20131956 (2010)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"2","key":"9439_CR30","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/0095-8956(88)90083-4","volume":"44","author":"F. Jaeger","year":"1988","unstructured":"Jaeger, F.: On Tutte polynomials and cycles of plane graphs. J. Comb. Theory Ser. B 44(2), 127\u2013146 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9439_CR31","volume-title":"Introduction to Parallel Algorithms","author":"J. JaJa","year":"1992","unstructured":"JaJa, J.: Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)"},{"key":"9439_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth. Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth. Computations and Approximations. Lecture Notes in Computer Science, vol.\u00a0842. Springer, Berlin (1994)"},{"key":"9439_CR33","series-title":"Colloq. Math. Soc. J\u00e1nos Bolyai","first-page":"451","volume-title":"Algebraic Methods in Graph Theory, Szeged, Hungary, 1978","author":"M. Las Vergnas","year":"1981","unstructured":"Las Vergnas, M.: Eulerian circuits of 4-valent graphs imbedded in surfaces. In: Algebraic Methods in Graph Theory, Szeged, Hungary, 1978. Colloq. Math. Soc. J\u00e1nos Bolyai, vol. 25, pp. 451\u2013477. North-Holland, Amsterdam (1981)"},{"key":"9439_CR34","first-page":"397","volume":"17","author":"M. Las Vergnas","year":"1983","unstructured":"Las Vergnas, M.: Le polyn\u00f4me de Martin d\u2019un graphe eulerian. Ann. Discrete Math. 17, 397\u2013411 (1983)","journal-title":"Ann. Discrete Math."},{"issue":"3","key":"9439_CR35","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/0095-8956(88)90079-2","volume":"45","author":"M. Las Vergnas","year":"1988","unstructured":"Las Vergnas, M.: On the evaluation at (3,3) of the Tutte polynomial of a graph. J. Comb. Theory Ser. B 45(3), 367\u2013372 (1988)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9439_CR36","unstructured":"Lecerf, G., Schost, \u00c9.: Fast multivariate power series multiplication in characteristic zero. SADIO Electron. J. 5(1) (2003)"},{"key":"9439_CR37","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes","author":"F.T. Leighton","year":"1992","unstructured":"Leighton, F.T.: Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann, San Mateo (1992)"},{"key":"9439_CR38","unstructured":"Martin, P.: Enum\u00e9rations Eul\u00e9riennes dans le multigraphes et invariants de Tutte\u2013Grothendieck. PhD thesis, Grenoble, France (1977)"},{"key":"9439_CR39","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1090\/S0002-9947-1987-0869224-1","volume":"299","author":"S. Negami","year":"1987","unstructured":"Negami, S.: Polynomial invariants of graphs. Trans. Am. Math. Soc. 299, 601\u2013622 (1987)","journal-title":"Trans. Am. Math. Soc."},{"issue":"3","key":"9439_CR40","doi-asserted-by":"crossref","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. Comb. Probab. Comput. 7(3), 307\u2013321 (1998)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"9439_CR41","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","volume":"95","author":"S.-i. Oum","year":"2005","unstructured":"Oum, S.-i.: Rank-width and vertex-minors. J. Comb. Theory Ser. B 95(1), 79\u2013100 (2005)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"4","key":"9439_CR42","doi-asserted-by":"crossref","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.D.: Approximating clique-width and branch-width. J. Comb. Theory, Ser. B 96(4), 514\u2013528 (2006)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9439_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1007\/11779360_31","volume-title":"Coding and Cryptography. International Workshop, WCC 2005, Bergen, Norway, March 14\u201318, 2005","author":"C. Riera","year":"2006","unstructured":"Riera, C., Parker, M.G.: One and two-variable interlace polynomials: A spectral interpretation. In: Coding and Cryptography. International Workshop, WCC 2005, Bergen, Norway, March 14\u201318, 2005. Lecture Notes in Computer Science, vol.\u00a03969, pp. 397\u2013411. Springer, Berlin (2006)"},{"key":"9439_CR44","doi-asserted-by":"crossref","unstructured":"Traldi, L.: Binary nullity, Euler circuits and interlace polynomials. Preprint (2009). arXiv:0903.4405v1","DOI":"10.1017\/S0963548309990381"},{"issue":"1","key":"9439_CR45","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1017\/S0963548309990381","volume":"19","author":"L. Traldi","year":"2010","unstructured":"Traldi, L.: Weighted interlace polynomials. Comb. Probab. Comput. 19(1), 133\u2013157 (2010)","journal-title":"Comb. Probab. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9439-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9439-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9439-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,3]],"date-time":"2021-11-03T16:56:17Z","timestamp":1635958577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9439-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,6]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9439"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9439-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,6]]}}}