Parameterized Complexity and Subexponential-Time Computability

DOI10.1007/978-3-642-30891-8_11zbMath1358.68122OpenAlexW200564616MaRDI QIDQ2908538

Iyad A. Kanj, Jian'er Chen

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

A Basic Parameterized Complexity Primer ⋮ 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
• 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

This page was built for publication: Parameterized Complexity and Subexponential-Time Computability