On Parameterized Exponential Time Complexity

DOI10.1007/978-3-642-02017-9_20MaRDI QIDQ3630202zbMATH OpenOpenAlexFDO

Authors Ge Xia, Jianer Chen, Iyad Kanj

Publication date 3 June 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02017-9_20

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On parameterized exponential time complexity
• On the existence of subexponential parameterized algorithms
• scientific article; zbMATH DE number 1756013
• On miniaturized problems in parameterized complexity theory
• Parameterized complexity: exponential speed-up for planar graph problems

Cited in

(7)

• On parameterized exponential time complexity
• Parameterized complexity and subexponential-time computability
• Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
• Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
• scientific article; zbMATH DE number 1754598 (Why is no real title available?)
• Exponential time paradigms through the polynomial time lens
• Exponential Time Complexity of the Permanent and the Tutte Polynomial

This page was built for publication: On Parameterized Exponential Time Complexity

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