Exponential Time Complexity of the Permanent and the Tutte Polynomial
From MaRDI portal
Publication:3587397
DOI10.1007/978-3-642-14165-2_37zbMath1288.68111OpenAlexW1786652263MaRDI QIDQ3587397
Thore Husfeldt, Martin Wahlen, Holger Dell
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
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Determinants, permanents, traces, other special matrix functions (15A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
Lower bound on SNARGs in the random oracle model ⋮ Fine-grained dichotomies for the Tutte plane and Boolean \#CSP ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ Exponential Time Complexity of Weighted Counting of Independent Sets ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected ⋮ Unnamed Item ⋮ Noncommutativity makes determinants hard
This page was built for publication: Exponential Time Complexity of the Permanent and the Tutte Polynomial
