Exponential time paradigms through the polynomial time lens

DOI10.4230/LIPICS.ESA.2016.36zbMATH Open1397.68097MaRDI QIDQ4606306FDOQ4606306

Jesper Nederlof, Rahul Santhanam, Andrew Drucker

Publication date: 2 March 2018

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

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)

Cited In (7)

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

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)