On parameterized exponential time complexity

DOI10.1016/J.TCS.2009.03.006zbMath1172.68023OpenAlexW2157494948MaRDI QIDQ1029333

Iyad A. Kanj, Ge Xia, Jian'er Chen

Publication date: 10 July 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.006

zbMATH Keywords

parameterized algorithmsparameterized complexityexact algorithmssubexponential time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Parameterized Complexity and Subexponential-Time Computability ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Refined memorization for vertex cover
• Strong computational lower bounds via parameterized complexity
• Which problems have strongly exponential complexity?
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• On the existence of subexponential parameterized algorithms
• On the computational hardness based on linear fpt-reductions
• Tight lower bounds for certain parameterized NP-hard problems
• Vertex Cover: Further Observations and Further Improvements
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Vertex packings: Structural properties and algorithms
• Nondeterminism within $P^ * $
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• On efficient fixed-parameter algorithms for weighted vertex cover
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: On parameterized exponential time complexity