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