scientific article; zbMATH DE number 7561374
From MaRDI portal
Publication:5091010
DOI10.4230/LIPIcs.ISAAC.2018.20MaRDI QIDQ5091010
Dimitrios M. Thilikos, Eun Jung Kim, Maria J. Serna
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1809.08160
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Compactors for parameterized counting problems ⋮ A Retrospective on (Meta) Kernelization ⋮ Sparse obstructions for minor-covering parameters ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Bidimensionality and Kernels
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- AND-compression of NP-complete problems: streamlined proof and minor observations
- Fundamentals of parameterized complexity
- Lower bounds for kernelizations and other preprocessing procedures
- Infeasibility of instance compression and succinct PCPs for NP
- Monadic second-order evaluations on tree-decomposable graphs
- Generalized model-checking over locally tree-decomposable classes
- The structure of the models of decidable monadic theories of graphs
- Efficient algorithms for counting parameterized list \(H\)-colorings
- On problems without polynomial kernels
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Reduction algorithms for graphs of small treewidth
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Kernelization – Preprocessing with a Guarantee
- On the Compressibility of $\mathcal{NP}$ Instances and Cryptographic Applications
- (Meta) Kernelization
- Easy problems for tree-decomposable graphs
- New Limits to Classical and Quantum Instance Compression
- Algorithmic Meta-theorems
- Deciding First-Order Properties of Nowhere Dense Graphs
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Kernelization Lower Bounds by Cross-Composition
- Losing Treewidth by Separating Subsets
- Algorithms and Data Structures
- Testing first-order properties for subclasses of sparse graphs
- Bidimensionality and Geometric Graphs
- Kernelizations for Parameterized Counting Problems
- Parameterized Algorithms
- On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
