Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping

DOI10.1093/LOGCOM/EXN029MaRDI QIDQ3611723zbMATH OpenOpenAlexFDO

Authors Yijia Chen, Jörg Flum

Publication date 2 March 2009

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exn029

zbMATH Keywords

exponential time complexityminiaturization mappingparameterized complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• On miniaturized problems in parameterized complexity theory
• Parameterized and Exact Computation
• On parameterized exponential time complexity

Cited in

(8)

• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Parameterized complexity and subexponential-time computability
• Parameterized and subexponential-time complexity of satisfiability problems and applications
• An Isomorphism Between Subexponential and Parameterized Complexity Theory
• Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
• Lower bounds for kernelizations and other preprocessing procedures
• On miniaturized problems in parameterized complexity theory
• Parameterized and subexponential-time complexity of satisfiability problems and applications

This page was built for publication: Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping

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