Fast evaluation of interlace polynomials on graphs of bounded treewidth
From MaRDI portal
Abstract: We consider the multivariate interlace polynomial introduced by Courcelle (2008), which generalizes several interlace polynomials defined by Arratia, Bollobas, and Sorkin (2004) and by Aigner and van der Holst (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 2008) employs a general logical framework and leads to an algorithm with running time f(k)*n, where f(k) is doubly exponential in k. 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)}*n arithmetic operations and can be efficiently implemented in parallel.
Recommendations
- Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- Evaluating a weighted graph polynomial for graphs of bounded tree-width
- Efficient computation of the characteristic polynomial of a tree and related tasks
- Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
- On the Complexity of the Interlace Polynomial
- Computing Graph Polynomials on Graphs of Bounded Clique-Width
- The complexity of evaluating interpolation polynomials
Cites work
- scientific article; zbMATH DE number 3739583 (Why is no real title available?)
- scientific article; zbMATH DE number 52113 (Why is no real title available?)
- scientific article; zbMATH DE number 107951 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1439417 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A Most General Edge Elimination Polynomial
- A Tutte Polynomial for Coloured Graphs
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- A partial k-arboretum of graphs with bounded treewidth
- A two-variable interlace polynomial
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Approximating clique-width and branch-width
- Binary nullity, Euler circuits and interlace polynomials
- Coding and Cryptography
- Distance Hereditary Graphs and the Interlace Polynomial
- Euler circuits and DNA sequencing by hybridization
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- Evaluations of the circuit partition polynomial
- Fast multivariate power series multiplication in characteristic zero
- Graph polynomials derived from Tutte-Martin polynomials
- Graphic presentations of isotropic systems
- Interlace polynomials
- Interlace polynomials: enumeration, unimodality and connections to codes
- Intractability of clique-width parameterizations
- Isotropic systems
- Le Polynôme De Martin D'un Graphe Eulerien
- New results for the Martin polynomial
- On Tutte polynomials and cycles of plane graphs
- On the Complexity of the Interlace Polynomial
- On the evaluation at (3,3) of the Tutte polynomial of a graph
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
- Polynomial Invariants of Graphs
- Rank-width and vertex-minors
- The interlace polynomial of a graph
- Treewidth. Computations and approximations
- Tutte-Martin polynomials and orienting vectors of isotropic systems
- Upper bounds to the clique width of graphs
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Weighted interlace polynomials
Cited in
(7)- A graph polynomial for independent sets of bipartite graphs
- Evaluating a weighted graph polynomial for graphs of bounded tree-width
- Decompositions of graphs of functions and fast iterations of lookup tables
- Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
- Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
This page was built for publication: Fast evaluation of interlace polynomials on graphs of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634679)
