Tutte polynomials computable in polynomial time

DOI10.1016/0012-365X(92)90289-RzbMATH Open0780.05011OpenAlexW2051679228MaRDI QIDQ686299FDOQ686299

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

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

zbMATH Keywords

matroidTutte polynomialpolynomial time

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Decomposition of regular matroids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the computational complexity of the Jones and Tutte polynomials
• The Computational Complexity of Tutte Invariants for Planar Graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A Combinatorial Model for Series-Parallel Networks
• A Linear-Time Algorithm for Computing K-Terminal Reliability in Series-Parallel Networks
• The Complexity of Reliability Computations in Planar and Acyclic Graphs
• A Combinatorial Decomposition Theory
• Title not available (Why is that?)
• The computational complexity of matroid properties
• On minors of non-binary matroids
• Title not available (Why is that?)
• The Tutte polynomial. I: General theory

Cited In (29)

• 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
• Weighted interlace polynomials
• The Tutte polynomial of some matroids
• 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
• Counting truth assignments of formulas of bounded tree-width or clique-width
• On zeros of the characteristic polynomial of matroids of bounded tree-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
• A tight relation between series-parallel graphs and bipartite distance hereditary graphs
• Splitting formulas for Tutte polynomials
• 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
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• Computing the Tutte polynomial of a matroid from its lattice of cyclic flats

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)