Fixed-parameter approximation: conceptual framework and approximability results
From MaRDI portal
(Redirected from Publication:2379929)
Recommendations
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On fixed-parameter tractability and approximability of NP optimization problems
- Mathematical Foundations of Computer Science 2004
- On Parameterized Approximability
- Polynomial time approximation schemes and parameterized complexity
Cites work
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1332665 (Why is no real title available?)
- scientific article; zbMATH DE number 563208 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Approximation algorithms for NP-complete problems on planar graphs
- Computing and Combinatorics
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Improved Parameterized Upper Bounds for Vertex Cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Mathematical Foundations of Computer Science 2004
- On Parameterized Approximability
- On fixed-parameter tractability and approximability of NP optimization problems
- On limited nondeterminism and the complexity of the V-C dimension
- On the Amount of Nondeterminism and the Power of Verifying
- On the efficiency of polynomial time approximation schemes
- On the existence of subexponential parameterized algorithms
- On the structure of parameterized problems in NP
- Optimization, approximation, and complexity classes
- Parameterized Approximation Problems
- Parameterized complexity: exponential speed-up for planar graph problems
- The inapproximability of non-NP-hard optimization problems.
Cited in
(13)- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- Hyper-T-width and hyper-D-width: Stable connectivity measures for hypergraphs
- The constant inapproximability of the parameterized dominating set problem
- Backdoors to satisfaction
- An exponential time 2-approximation algorithm for bandwidth
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Parameterized approximation via fidelity preserving transformations
- Improved approximations for hard optimization problems via problem instance classification
- Polynomial kernelizations for \(\text{MIN} \text{F}^+ \Pi_1\) and \(\text{MAX NP}\)
- Parameterized Approximation Problems
- Data reductions and combinatorial bounds for improved approximation algorithms
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Fixed-Parameter and Approximation Algorithms: A New Look
This page was built for publication: Fixed-parameter approximation: conceptual framework and approximability results
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379929)