A Basic Parameterized Complexity Primer
From MaRDI portal
Publication:2908536
DOI10.1007/978-3-642-30891-8_9zbMath1358.68130OpenAlexW1511559439MaRDI QIDQ2908536
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The Birth and Early Years of Parameterized Complexity ⋮ What’s Next? Future Directions in Parameterized Complexity
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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Confronting intractability via parameters
- Lower bounds for kernelizations and other preprocessing procedures
- Infeasibility of instance compression and succinct PCPs for NP
- Heuristic algorithms in computational molecular biology
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding odd cycle transversals.
- Improved upper bounds for vertex cover
- Matroid tree-width
- Parameterized approximation of dominating set problems
- On problems without polynomial kernels
- Nonconstructive advances in polynomial-time complexity
- Parameterized circuit complexity and the \(W\) hierarchy
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On fixed-parameter tractability and approximability of NP optimization problems
- On the parameterized complexity of short computation and factorization
- Which problems have strongly exponential complexity?
- 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
- On the existence of subexponential parameterized algorithms
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Bounded fixed-parameter tractability and reducibility
- Crown structures for vertex cover kernelization
- A faster FPT algorithm for the maximum agreement forest problem
- The complexity of polynomial-time approximation
- Scalable parallel algorithms for FPT problems
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized counting problems
- Über eine Eigenschaft der ebenen Komplexe
- Color-coding
- Beyond NP-completeness for problems of bounded width (extended abstract)
- A polynomial time approximation scheme for general multiprocessor job scheduling (extended abstract)
- The Birth and Early Years of Parameterized Complexity
- Kernelization – Preprocessing with a Guarantee
- Parameterized Complexity and Subexponential-Time Computability
- Fixed-Parameter Tractability of Treewidth and Pathwidth
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Backdoors to Satisfaction
- Studies in Computational Aspects of Voting
- A Parameterized Halting Problem
- What’s Next? Future Directions in Parameterized Complexity
- Clique-width minimization is NP-hard
- Integer Programming with a Fixed Number of Variables
- Intractability of Clique-Width Parameterizations
- Deciding first-order properties of locally tree-decomposable structures
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Randomized Approximations of Parameterized Counting Problems
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- On Problems without Polynomial Kernels (Extended Abstract)
- Clique-Width is NP-Complete
- Graph minors. II. Algorithmic aspects of tree-width
- Nonconstructive tools for proving polynomial-time decidability
- Vertex packings: Structural properties and algorithms
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Inferring Evolutionary History From DNA Sequences
- On Interpolation and Automatization for Frege Systems
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- (Meta) Kernelization
- A linear time algorithm for finding tree-decompositions of small treewidth
- Paths, Trees, and Flowers
- Finding topological subgraphs is fixed-parameter tractable
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Ordering by Divisibility in Abstract Algebras
