Tutte polynomials computable in polynomial time

DOI10.1016/0012-365X(92)90289-RMaRDI QIDQ686299zbMATH OpenOpenAlexFDO

Authors James Oxley, D. J. A. Welsh

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)

Recommendations

• The Tutte Polynomial for Matroids of Bounded Branch-Width
• Complexity of graph polynomials
• Splitting formulas for Tutte polynomials
• On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width

Cites work

• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 3719168 (Why is no real title available?)
• scientific article; zbMATH DE number 3784908 (Why is no real title available?)
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• A Combinatorial Decomposition Theory
• A Combinatorial Model for Series-Parallel Networks
• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
• Decomposition of regular matroids
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On minors of non-binary matroids
• On the computational complexity of the Jones and Tutte polynomials
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• The Computational Complexity of Tutte Invariants for Planar Graphs
• The Tutte polynomial. I: General theory
• The computational complexity of matroid properties

Cited in

(29)

• Computing the Tutte polynomial of a matroid from its lattice of cyclic flats
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Parallel connections and coloured Tutte polynomials
• The computational complexity of knot and matroid polynomials
• Evaluations of topological Tutte polynomials
• Distance Hereditary Graphs and the Interlace Polynomial
• Algorithmic uses of the Feferman-Vaught theorem
• COMPUTING THE JONES POLYNOMIAL ON BIPARTITE GRAPHS
• The exact complexity of the Tutte polynomial
• Series-parallel posets and the Tutte polynomial
• Complexity of graph polynomials
• Bicycle dimension and special points of the Tutte polynomial
• The Tutte polynomial of some matroids
• Weighted interlace polynomials
• On the Complexity of Computing the Tutte Polynomial of Bicircular Matroids
• Sylow's theorem in polynomial time
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• On zeros of the characteristic polynomial of matroids of bounded tree-width
• Counting truth assignments of formulas of bounded tree-width or clique-width
• On the algebraic complexity of some families of coloured Tutte polynomials
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• The Tutte polynomial modulo a prime
• Amalgam width of matroids
• Splitting formulas for Tutte polynomials
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• From a zoo to a zoology: Towards a general theory of graph polynomials
• The Homfly and dichromatic polynomials
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Jones polynomial of knots formed by repeated tangle replacement operations

This page was built for publication: Tutte polynomials computable in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q686299)