The Birth and Early Years of Parameterized Complexity
From MaRDI portal
Publication:2908529
DOI10.1007/978-3-642-30891-8_2zbMath1358.68129OpenAlexW30204139MaRDI QIDQ2908529
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_2
Related Items
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths, A Basic Parameterized Complexity Primer, Cameo of a Consummate Computabilist, Surfing with Rod
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
- Fundamentals of parameterized complexity
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Advice classes of parametrized tractability
- The isomorphism problem for torsion-free abelian groups is analytic complete
- NP is as easy as detecting unique solutions
- Nonconstructive advances in polynomial-time complexity
- Parameterized circuit complexity and the \(W\) hierarchy
- Optimization, approximation, and complexity classes
- Threshold dominating sets and an improved characterization of \(W[2\)]
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On fixed-parameter tractability and approximability of NP optimization problems
- The parameterized complexity of sequence alignment and consensus
- On the parameterized complexity of short computation and factorization
- Which problems have strongly exponential complexity?
- Parameterized complexity of finding subgraphs with hereditary properties.
- Uniformly hard languages.
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
- Color-coding
- Beyond NP-completeness for problems of bounded width (extended abstract)
- A Basic Parameterized Complexity Primer
- What’s Next? Future Directions in Parameterized Complexity
- Integer Programming with a Fixed Number of Variables
- Algorithmic Randomness and Complexity
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Parameterized Derandomization
- On Problems without Polynomial Kernels (Extended Abstract)
- Graph minors. II. Algorithmic aspects of tree-width
- Nonconstructive tools for proving polynomial-time decidability
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- On the Structure of Polynomial Time Reducibility
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Inferring Evolutionary History From DNA Sequences
- Fixed-Parameter Tractability and Completeness I: Basic Results
- The Parametrized Complexity of Some Fundamental Problems in Coding Theory
- A linear time algorithm for finding tree-decompositions of small treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
