Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
DOI10.1007/978-3-642-14165-2_37zbMATH Open1288.68111OpenAlexW1786652263MaRDI QIDQ3587397FDOQ3587397
Authors: Holger Dell, Thore Husfeldt, Martin Wahlen 
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_37
Recommendations
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Block interpolation: a framework for tight exponential-time counting complexity
- Block interpolation: a framework for tight exponential-time counting complexity
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15)
Cited In (10)
- Fine-grained dichotomies for the Tutte plane and Boolean \#CSP
- Title not available (Why is that?)
- Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
- Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions
- Noncommutativity makes determinants hard
- Exponential time complexity of the complex weighted Boolean \#CSP
- The exponential time complexity of computing the probability that a graph is connected
- Exponential Time Complexity of Weighted Counting of Independent Sets
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- Lower bound on SNARGs in the random oracle model
This page was built for publication: Exponential time complexity of the permanent and the Tutte polynomial (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587397)
