Inapproximability of the Tutte polynomial
type: Item
instance of: scholarly article
title: Inapproximability of the Tutte polynomial
zbMATH Open document ID: 1153.68039
author: Leslie Ann Goldberg
author: Mark Jerrum
published in: Information and Computation
publication date: 2008-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/cs/0605140
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5312291
MaRDI profile type: Publication
OpenAlex ID: W2122765404
Wikidata QID: Q55879601
arXiv ID: cs/0605140
cites work: Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
cites work: The Tutte Polynomial Part I: General Theory
cites work: The Complexity of Multiterminal Cuts
cites work: The relative complexity of approximate counting problems
cites work: Q4521549
cites work: Approximation Algorithms for Several Graph Augmentation Problems
cites work: Q4198056
cites work: Q3549645
cites work: On the computational complexity of the Jones and Tutte polynomials
cites work: Q4798347
cites work: Polynomial-Time Approximation Algorithms for the Ising Model
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem
cites work: Hard Enumeration Problems in Geometry and Combinatorics
cites work: Nowhere-zero 6-flows
cites work: A Contribution to the Theory of Chromatic Polynomials
cites work: Q3216652
cites work: NP is as easy as detecting unique solutions
cites work: Q3140234
cites work: Randomised Approximation in the Tutte Plane
cites work: On Unapproximable Versions of $NP$-Complete Problems
DOI: 10.1016/J.IC.2008.04.003
description: scientific article