Parameterized Complexity and Subexponential-Time Computability
From MaRDI portal
Publication:2908538
DOI10.1007/978-3-642-30891-8_11zbMath1358.68122MaRDI QIDQ2908538
Publication date: 5 September 2012
Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_11
68Q25: Analysis of algorithms and problem complexity
Related Items
Parameterized and subexponential-time complexity of satisfiability problems and applications, A Basic Parameterized Complexity Primer, 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
- Improved deterministic algorithms for weighted matching and packing problems
- An improved deterministic local search algorithm for 3-SAT
- On miniaturized problems in parameterized complexity theory
- Strong computational lower bounds via parameterized complexity
- Polynomial time approximation schemes and parameterized complexity
- Finding paths of length \(k\) in \(O^{*}(2^k)\) time
- On parameterized exponential time complexity
- Characterizing parallel hierarchies by reducibilities
- Optimization, approximation, and complexity classes
- Fixed-parameter algorithms for CLOSEST STRING and related problems
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- The complexity of polynomial-time approximation
- Tight lower bounds for certain parameterized NP-hard problems
- Vertex Cover: Further Observations and Further Improvements
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Faster Algebraic Algorithms for Path and Packing Problems
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
- Algorithms for maximum independent sets
- On the Amount of Nondeterminism and the Power of Verifying
- Color-coding
- Circuit Bottom Fan-in and Computational Power
- Genetic Design of Drugs Without Side-Effects
- Fundamentals of Computation Theory
- On the complexity of \(k\)-SAT
