The Computational Complexity of Tutte Invariants for Planar Graphs
From MaRDI portal
Publication:5470709
DOI10.1137/S0097539704446797zbMath1089.05017OpenAlexW2011473996WikidataQ30049061 ScholiaQ30049061MaRDI QIDQ5470709
Publication date: 1 June 2006
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704446797
reliabilitypercolationplanar graphsenumerationPotts modelTutte polynomialpolynomial timeknot polynomials\(\#P\)-complete
Combinatorial identities, bijective combinatorics (05A19) Graph theory (including graph drawing) in computer science (68R10) Percolation (82B43) Combinatorial aspects of matroids and geometric lattices (05B35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Sixty years of network reliability ⋮ The complexity of approximating the complex-valued Potts model ⋮ Computing the Tutte polynomial of Archimedean tilings ⋮ Network reliability and the probabilistic estimation of damage from fire spread ⋮ A new approach to solving three combinatorial enumeration problems on planar graphs ⋮ The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems ⋮ Complexity of Ising Polynomials ⋮ Graph parameters from symplectic group invariants ⋮ Edge cut splitting formulas for Tutte-Grothendieck invariants ⋮ Inapproximability of the Tutte polynomial of a planar graph ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Unnamed Item ⋮ The Tutte polynomial modulo a prime ⋮ Combinatorial aspects of network reliability ⋮ Modifications of Tutte–Grothendieck invariants and Tutte polynomials ⋮ Tutte polynomials computable in polynomial time ⋮ The complexity of planar Boolean \#CSP with complex weights ⋮ A little statistical mechanics for the graph theorist ⋮ Interpretations of the Tutte and characteristic polynomials of matroids ⋮ Complexity classes as mathematical axioms ⋮ A Graph Integral Formulation of the Circuit Partition Polynomial ⋮ FKT is not universal -- a planar holant dichotomy for symmetric constraints ⋮ The complexity of approximating the complex-valued Potts model ⋮ The complexity of computing the Tutte polynomial on transversal matroids ⋮ An algorithm for the Tutte polynomials of graphs of bounded treewidth ⋮ Interpretations of the Tutte polynomials of regular matroids ⋮ COLORING PLANAR GRAPHS VIA COLORED PATHS IN THE ASSOCIAHEDRA ⋮ The computational complexity of knot and matroid polynomials ⋮ Planar graph coloring is not self-reducible, assuming P\(\neq NP\) ⋮ Network reliability: Numbers or insight? (A discussion paper) ⋮ A dichotomy for real weighted Holant problems
