Tutte polynomials computable in polynomial time

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

James G. Oxley, Dominic J. A. Welsh

Publication date: 14 October 1993

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

zbMATH Keywords

matroid; Tutte polynomial; polynomial time

Mathematics Subject Classification ID

05B35: Combinatorial aspects of matroids and geometric lattices

Related Items

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

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