The Birth and Early Years of Parameterized Complexity
From MaRDI portal
Publication:2908529
DOI10.1007/978-3-642-30891-8_2zbMATH Open1358.68129OpenAlexW30204139MaRDI QIDQ2908529FDOQ2908529
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
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)
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)