On parameterized exponential time complexity
From MaRDI portal
Publication:1029333
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
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
