Exponential time paradigms through the polynomial time lens

DOI10.4230/LIPICS.ESA.2016.36MaRDI QIDQ4606306zbMATH OpenFDO

Authors Andrew Drucker, Jesper Nederlof, Rahul Santhanam

Publication date 2 March 2018

zbMATH Keywords

dynamic programminglower boundsbranchingexponential-time paradigms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On parameterized exponential time complexity
• On Parameterized Exponential Time Complexity
• On two techniques of combining branching and treewidth
• On the existence of subexponential parameterized algorithms
• Lower bounds for dynamic programming on planar graphs of bounded cutwidth

Cited in

(7)

• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• Towards the Actual Relationship Between NP and Exponential Time
• Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
• Width, depth, and space: tradeoffs between branching and dynamic programming
• The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis

This page was built for publication: Exponential time paradigms through the polynomial time lens

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4606306)