Inapproximability of the Tutte polynomial
Authors:
Open Access
- 11 June 2007
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 459-468
Abstract
No abstract availableKeywords
All Related Versions
This publication has 15 references indexed in Scilit:
- The Relative Complexity of Approximate Counting ProblemsAlgorithmica, 2003
- A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability ProblemSIAM Review, 2001
- On Unapproximable Versions of $NP$-Complete ProblemsSIAM Journal on Computing, 1996
- Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense caseRandom Structures & Algorithms, 1995
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- Polynomial-Time Approximation Algorithms for the Ising ModelSIAM Journal on Computing, 1993
- On the computational complexity of the Jones and Tutte polynomialsMathematical Proceedings of the Cambridge Philosophical Society, 1990
- Random generation of combinatorial structures from a uniform distributionTheoretical Computer Science, 1986
- Approximation Algorithms for Several Graph Augmentation ProblemsSIAM Journal on Computing, 1981
- Nowhere-zero 6-flowsJournal of Combinatorial Theory, Series B, 1981