The Birth and Early Years of Parameterized Complexity

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Fundamentals of parameterized complexity
Optimization, approximation, and complexity classes
Fixed-parameter tractability of graph modification problems for hereditary properties
Algorithmic Randomness and Complexity
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Which problems have strongly exponential complexity?
Integer Programming with a Fixed Number of Variables
Nonconstructive tools for proving polynomial-time decidability
On the Structure of Polynomial Time Reducibility
Parameterizing above Guaranteed Values: MaxSat and MaxCut
Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
Graph minors. II. Algorithmic aspects of tree-width
Fixed-Parameter Tractability and Completeness I: Basic Results
A linear time algorithm for finding tree-decompositions of small treewidth
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Fixed-parameter tractability and completeness II: On completeness for W[1]
NP is as easy as detecting unique solutions
Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
Advice classes of parametrized tractability
The Parametrized Complexity of Some Fundamental Problems in Coding Theory
A Basic Parameterized Complexity Primer
Parameterized circuit complexity and the \(W\) hierarchy
Parameterized complexity of finding subgraphs with hereditary properties.
Uniformly hard languages.
Nonconstructive advances in polynomial-time complexity
Resolution Is Not Automatizable Unless W[P] Is Tractable
Threshold dominating sets and an improved characterization of \(W[2]\)
A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract)
Inferring Evolutionary History From DNA Sequences
The parameterized complexity of sequence alignment and consensus
On the parameterized complexity of short computation and factorization
The isomorphism problem for torsion-free abelian groups is analytic complete
Parameterized Derandomization
On Problems without Polynomial Kernels (Extended Abstract)
\(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
What’s Next? Future Directions in Parameterized Complexity
On fixed-parameter tractability and approximability of NP optimization problems

Cited In (6)

Cameo of a Consummate Computabilist
A Basic Parameterized Complexity Primer
Surfing with Rod
Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
A brief history of NP-completeness, 1954--2012
The Turing way to parameterized complexity

This page was built for publication: The Birth and Early Years of Parameterized Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908529)