An algorithm for the Tutte polynomials of graphs of bounded treewidth

DOI10.1016/S0012-365X(98)00113-7zbMath0955.05101MaRDI QIDQ1584397

Artur Andrzejak

Publication date: 2 November 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

algorithmcomputational complexitytreewidthTutte polynomial

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Jones polynomial of knots formed by repeated tangle replacement operations, Fixed-Parameter Tractability of Treewidth and Pathwidth, Complexity of Ising Polynomials, Algorithmic uses of the Feferman-Vaught theorem, Farrell polynomials on graphs of bounded tree width, Simultaneous optimisation of clustering quality and approximation error for time series segmentation, Fast evaluation of interlace polynomials on graphs of bounded treewidth, Complexity and approximability of the cover polynomial, The enumeration of vertex induced subgraphs with respect to the number of components, Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width, On the algebraic complexity of some families of coloured Tutte polynomials, The Potts model and the Tutte polynomial, Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, On the colored Tutte polynomial of a graph of bounded treewidth, FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES, From a zoo to a zoology: Towards a general theory of graph polynomials, Spanning tree constrained determinantal point processes are hard to (approximately) evaluate, Parameterized counting problems, Forests, colorings and acyclic orientations of the square lattice, Counting \(H-\)colorings of partial \(k-\)trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tutte polynomials computable in polynomial time
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• The computational complexity of knot and matroid polynomials
• Splitting formulas for Tutte polynomials
• The Tutte polynomial of a graph, depth-first search, and simplicial complex partitions
• Easy problems for tree-decomposable graphs
• Polynomial Invariants of Graphs
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• The Parallel Evaluation of General Arithmetic Expressions
• Parallel algorithms with optimal speedup for bounded treewidth
• On the computational complexity of the Jones and Tutte polynomials
• The Computational Complexity of Tutte Invariants for Planar Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth