Fast evaluation of interlace polynomials on graphs of bounded treewidth
DOI10.1007/s00453-010-9439-4zbMath1227.05167arXiv0902.1693OpenAlexW2145782763MaRDI QIDQ634679
Christian Hoffmann, Markus Bläser
Publication date: 16 August 2011
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0902.1693
Gaussian eliminationadjacency matrixtree decompositionparameterized algorithmmultivariate interlace polynomial
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A two-variable interlace polynomial
- The interlace polynomial of a graph
- Vertex-minors, monadic second-order logic, and a conjecture by Seese
- Interlace polynomials: enumeration, unimodality and connections to codes
- A multivariate interlace polynomial and its computation for graphs of bounded clique-width
- On Tutte polynomials and cycles of plane graphs
- Isotropic systems
- Graphic presentations of isotropic systems
- On the evaluation at (3,3) of the Tutte polynomial of a graph
- Tutte-Martin polynomials and orienting vectors of isotropic systems
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Interlace polynomials
- New results for the Martin polynomial
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Euler circuits and DNA sequencing by hybridization
- Evaluations of the circuit partition polynomial
- Upper bounds to the clique width of graphs
- Binary nullity, Euler circuits and interlace polynomials
- Approximating clique-width and branch-width
- Rank-width and vertex-minors
- Graph polynomials derived from Tutte-Martin polynomials
- Intractability of Clique-Width Parameterizations
- Le Polynôme De Martin D'un Graphe Eulerien
- Weighted Interlace Polynomials
- Polynomial Invariants of Graphs
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- A Tutte Polynomial for Coloured Graphs
- On the Complexity of the Interlace Polynomial
- A Most General Edge Elimination Polynomial
- Distance Hereditary Graphs and the Interlace Polynomial
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Coding and Cryptography
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
This page was built for publication: Fast evaluation of interlace polynomials on graphs of bounded treewidth
