On the computational hardness based on linear fpt-reductions
From MaRDI portal
Publication:2498987
DOI10.1007/s10878-006-7137-6zbMath1130.90064OpenAlexW2041837101MaRDI QIDQ2498987
Xiuzhen Huang, Ge Xia, Iyad A. Kanj, Jian'er Chen
Publication date: 14 August 2006
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-006-7137-6
Related Items (10)
Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ An improved lower bound on approximation algorithms for the closest substring problem ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ On parameterized exponential time complexity ⋮ Kernelization: New Upper and Lower Bound Techniques
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- Structure preserving reductions among convex optimization problems
- Characterizing parallel hierarchies by reducibilities
- Optimization, approximation, and complexity classes
- On the complexity of database queries
- The minimum feature set problem
- On fixed-parameter tractability and approximability of NP optimization problems
- On limited nondeterminism and the complexity of the V-C dimension
- The inapproximability of non-NP-hard optimization problems.
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- On the existence of subexponential parameterized algorithms
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- Tight lower bounds for certain parameterized NP-hard problems
- Vertex Cover: Further Observations and Further Improvements
- Linear FPT reductions and computational lower bounds
- Finding a Maximum Independent Set
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Model-Checking Problems as a Basis for Parameterized Intractability
- Mathematical Foundations of Computer Science 2004
- Automata, Languages and Programming
This page was built for publication: On the computational hardness based on linear fpt-reductions
