Parameterized computation and complexity: a new approach dealing with NP-hardness
From MaRDI portal
Publication:2576825
DOI10.1007/s11390-005-0003-7zbMath1258.68065OpenAlexW1986447712MaRDI QIDQ2576825
Publication date: 29 December 2005
Published in: Journal of Computer Science and Technology (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s11390-005-0003-7
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Augmenting weighted graphs to establish directed point-to-point connectivity, A practical exact algorithm for the individual haplotyping problem MEC/GI, On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]], An improved lower bound on approximation algorithms for the closest substring problem, Unnamed Item, An improved FPT algorithm for the flip distance problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the efficiency of polynomial time approximation schemes
- An improved fixed-parameter algorithm for vertex cover
- Matrix multiplication via arithmetic progressions
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Toward a unified approach for the classification of NP-complete optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Optimization, approximation, and complexity classes
- On the complexity of database queries
- On fixed-parameter tractability and approximability of NP optimization problems
- Diameter and treewidth in minor-closed graph families
- Which problems have strongly exponential complexity?
- A general method to speed up fixed-parameter-tractable algorithms
- On limited nondeterminism and the complexity of the V-C dimension
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The inapproximability of non-NP-hard optimization problems.
- Solving large FPT problems on coarse-grained parallel machines
- On the existence of subexponential parameterized algorithms
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Using nondeterminism to design efficient deterministic algorithms
- Graph minors. XIII: The disjoint paths problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Approximation properties of NP minimization classes
- On the structure of parameterized problems in NP
- Tight lower bounds for certain parameterized NP-hard problems
- Graph minors. VIII: A Kuratowski theorem for general surfaces
- Vertex Cover: Further Observations and Further Improvements
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Proof verification and the hardness of approximation problems
- Linear FPT reductions and computational lower bounds
- Polynomial-time data reduction for dominating set
- Algorithms for maximum independent sets
- Nonconstructive tools for proving polynomial-time decidability
- Applications of a Planar Separator Theorem
- Vertex packings: Structural properties and algorithms
- Finding a Maximum Independent Set
- Approximation algorithms for NP-complete problems on planar graphs
- Color-coding
- Genetic Design of Drugs Without Side-Effects
- The complexity of type inference for higher-order typed lambda calculi
- An efficient parameterized algorithm for m-set packing
- Computer Science Logic
- Mathematical Foundations of Computer Science 2004
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Fundamentals of Computation Theory
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
