On the algebraic complexity of some families of coloured Tutte polynomials
From MaRDI portal
Publication:1433009
DOI10.1016/S0196-8858(03)00087-3zbMath1041.05042OpenAlexW2037760470MaRDI QIDQ1433009
Martin Lotz, Johann A. Makowsky
Publication date: 15 June 2004
Published in: Advances in Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0196-8858(03)00087-3
Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
A Dichotomy Theorem for Polynomial Evaluation, Algorithmic uses of the Feferman-Vaught theorem, Complexity of the Bollobás-Riordan Polynomial, Uniform Algebraic Reducibilities between Parameterized Numeric Graph Invariants, Complexity and approximability of the cover polynomial, Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions, From a zoo to a zoology: Towards a general theory of graph polynomials
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Tutte polynomials computable in polynomial time
- A weighted graph polynomial from chromatic invariants of knots
- Gap-definable counting classes
- The complexities of the coefficients of the Tutte polynomial
- Completeness and reduction in algebraic complexity theory
- Counting problems over the reals
- An algorithm for the Tutte polynomials of graphs of bounded treewidth
- Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
- A symmetric function generalization of the chromatic polynomial of a graph
- Cook's versus Valiant's hypothesis
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
- A Dichromatic Polynomial for Weighted Graphs and Link Polynomials
- A complexity theory based on Boolean algebra
- Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
- A Tutte Polynomial for Coloured Graphs
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
- Randomised Approximation in the Tutte Plane
- On the computational complexity of the Jones and Tutte polynomials
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
