Tutte polynomials computable in polynomial time

DOI10.1016/0012-365X(92)90289-RzbMath0780.05011OpenAlexW2051679228MaRDI QIDQ686299

Dominic J. A. Welsh, James G. Oxley

Publication date: 14 October 1993

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

Full work available at URL: https://doi.org/10.1016/0012-365x(92)90289-r

zbMATH Keywords

matroidTutte polynomialpolynomial time

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Related Items

A tight relation between series-parallel graphs and bipartite distance hereditary graphs, Jones polynomial of knots formed by repeated tangle replacement operations, COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS, Splitting formulas for Tutte polynomials, Algorithmic uses of the Feferman-Vaught theorem, Evaluations of Topological Tutte Polynomials, On the algebraic complexity of some families of coloured Tutte polynomials, The Homfly and dichromatic polynomials, Weighted Interlace Polynomials, Counting truth assignments of formulas of bounded tree-width or clique-width, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Distance Hereditary Graphs and the Interlace Polynomial, Parallel connections and coloured Tutte polynomials, From a zoo to a zoology: Towards a general theory of graph polynomials, An algorithm for the Tutte polynomials of graphs of bounded treewidth, The computational complexity of knot and matroid polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Decomposition of regular matroids
• On minors of non-binary matroids
• The Tutte Polynomial Part I: General Theory
• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• The computational complexity of matroid properties
• A Combinatorial Decomposition Theory
• On the computational complexity of the Jones and Tutte polynomials
• The Computational Complexity of Tutte Invariants for Planar Graphs
• A Combinatorial Model for Series-Parallel Networks