A basic parameterized complexity primer
From MaRDI portal
Publication:2908536
DOI10.1007/978-3-642-30891-8_9zbMATH Open1358.68130OpenAlexW1511559439MaRDI QIDQ2908536FDOQ2908536
Authors: Rodney G. Downey 
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_9
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Paths, Trees, and Flowers
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Finding odd cycle transversals.
- On problems without polynomial kernels
- Which problems have strongly exponential complexity?
- Scalable parallel algorithms for FPT problems
- Über eine Eigenschaft der ebenen Komplexe
- Kernelization -- preprocessing with a guarantee
- Backdoors to satisfaction
- Integer Programming with a Fixed Number of Variables
- Clique-width is NP-complete
- Nonconstructive tools for proving polynomial-time decidability
- Title not available (Why is that?)
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Graph minors. II. Algorithmic aspects of tree-width
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- (Meta) Kernelization
- A linear time algorithm for finding tree-decompositions of small treewidth
- Infeasibility of instance compression and succinct PCPs for NP
- Improved upper bounds for vertex cover
- On the existence of subexponential parameterized algorithms
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Intractability of clique-width parameterizations
- Deciding first-order properties of locally tree-decomposable structures
- Studies in Computational Aspects of Voting
- Title not available (Why is that?)
- A faster FPT algorithm for the maximum agreement forest problem
- Finding topological subgraphs is fixed-parameter tractable
- Matroid tree-width
- Crown structures for vertex cover kernelization
- Title not available (Why is that?)
- Tight lower bounds for certain parameterized NP-hard problems
- Fixed-parameter tractability of treewidth and pathwidth
- Ordering by Divisibility in Abstract Algebras
- Parameterized circuit complexity and the \(W\) hierarchy
- A general method to speed up fixed-parameter-tractable algorithms
- Parameterized complexity of finding subgraphs with hereditary properties.
- Solving large FPT problems on coarse-grained parallel machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for kernelizations and other preprocessing procedures
- Parameterized approximation of dominating set problems
- Nonconstructive advances in polynomial-time complexity
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- Title not available (Why is that?)
- On Interpolation and Automatization for Frege Systems
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Title not available (Why is that?)
- 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
- On the parameterized complexity of short computation and factorization
- Parameterized complexity and subexponential-time computability
- Title not available (Why is that?)
- The complexity of polynomial-time approximation
- Parameterized counting problems
- Randomized Approximations of Parameterized Counting Problems
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Confronting intractability via parameters
- Methods for algorithmic meta theorems
- On Problems without Polynomial Kernels (Extended Abstract)
- Heuristic algorithms in computational molecular biology
- Polynomial-time approximation schemes for geometric graphs
- Clique-width minimization is NP-hard
- A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract)
- What's next? Future directions in parameterized complexity
- On fixed-parameter tractability and approximability of NP optimization problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- The birth and early years of parameterized complexity
- Bounded fixed-parameter tractability and reducibility
- A Parameterized Halting Problem
Cited In (6)
This page was built for publication: A basic parameterized complexity primer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908536)
