caa a22 4500 445805102 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9439-4 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9439-4 Fast Evaluation of Interlace Polynomials on Graphs ofBounded Treewidth [Elektronische Daten] [Markus Bläser, Christian Hoffmann] We consider the multivariate interlace polynomial introduced by Courcelle (Electron. J.Comb. 15(1), 2008), which generalizes several interlace polynomials defined by Arratia, Bollobás, and Sorkin (J. Comb. Theory Ser. B 92(2):199-233, 2004) and by Aigner and van der Holst (Linear Algebra Appl., 2004). We present an algorithm to evaluate the multivariate interlace polynomial of a graph with n vertices given a tree decomposition of the graph of width k. The best previously known result (Courcelle, Electron. J.Comb. 15(1), 2008) employs a general logical framework and leads to an algorithm with running time f(k)⋅n, where f(k) is doubly exponential ink. Analyzing the GF(2)-rank of adjacency matrices in the context of tree decompositions, we give a faster and more direct algorithm. Our algorithm uses $2^{3k^{2}+O(k)}\cdot n$ arithmetic operations and can be efficiently implemented in parallel. Springer Science+Business Media, LLC, 2010 Parameterized algorithm nationallicence Tree decomposition nationallicence Interlace polynomial nationallicence Adjacency matrix nationallicence Gaussian elimination nationallicence Bläser Markus Fachbereich Informatik, Universität des Saarlandes, Postfach 151150, 66041, Saarbrücken, Germany aut Hoffmann Christian Fachbereich Informatik, Universität des Saarlandes, Postfach 151150, 66041, Saarbrücken, Germany aut Algorithmica Springer-Verlag 61/1(2011-09-01), 3-35 0178-4617 61:1<3 2011 61 453 https://doi.org/10.1007/s00453-010-9439-4 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9439-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bläser Markus Fachbereich Informatik, Universität des Saarlandes, Postfach 151150, 66041, Saarbrücken, Germany aut NATIONALLICENCE 700 1- Hoffmann Christian Fachbereich Informatik, Universität des Saarlandes, Postfach 151150, 66041, Saarbrücken, Germany aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 3-35 0178-4617 61:1<3 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer