A Retrospective on (Meta) Kernelization
From MaRDI portal
Publication:5042460
DOI10.1007/978-3-030-42071-0_16OpenAlexW3020640542MaRDI QIDQ5042460
Publication date: 19 October 2022
Published in: Treewidth, Kernels, and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-42071-0_16
separabilitytreewidthparameterized algorithmsbidimensionalityfinite integer indexkernelization algorithmsmonadic second order logicparameterized problemsprotrusion decompositionsalgorithmic meta-theorems finite index
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Kernelization using structural parameters on sparse graph classes
- Fundamentals of parameterized complexity
- Lower bounds on kernelization
- A linear kernel for planar red-blue dominating set
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. XX: Wagner's conjecture
- Experiments on data reduction for optimal domination in networks
- Meta-kernelization with structural parameters
- Linearity of grid minors in treewidth with applications through bidimensionality
- On problems without polynomial kernels
- The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- A partial k-arboretum of graphs with bounded treewidth
- Treewidth. Computations and approximations
- Reduction algorithms for graphs of small treewidth
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Contraction obstructions for treewidth
- Meta-kernelization using well-structured modulators
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Vertex Cover: Further Observations and Further Improvements
- Graph Minors and Parameterized Algorithm Design
- Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey
- Bidimensionality of Geometric Intersection Graphs
- (Meta) Kernelization
- Explicit Linear Kernels via Dynamic Programming
- Deciding first-order properties of locally tree-decomposable structures
- Easy problems for tree-decomposable graphs
- The Bidimensional Theory of Bounded-Genus Graphs
- A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
- Algorithmic Meta-theorems
- A Linear Kernel for Planar Feedback Vertex Set
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
- Polynomial-time data reduction for dominating set
- A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
- The Parameterized Complexity of the Induced Matching Problem in Planar Graphs
- Linear Kernel for Planar Connected Dominating Set
- Contraction Bidimensionality: The Accurate Picture
- The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
- An algebraic theory of graph reduction
- Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors
- Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
- Kernelization
- Fixed-Parameter Tractability and Completeness I: Basic Results
- On the Induced Matching Problem
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- Contraction-Bidimensionality of Geometric Intersection Graphs
- (Meta) Kernelization
- Bidimensional Parameters and Local Treewidth
- Solving d-SAT via Backdoors to Small Treewidth
- Bidimensionality and Parameterized Algorithms (Invited Talk)
- Bidimensionality and Geometric Graphs
- Finding topological subgraphs is fixed-parameter tractable
- Linear Problem Kernels for NP-Hard Problems on Planar Graphs
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Encyclopedia of Algorithms
- On reduction algorithms for graphs with small treewidth
- Reduction algorithms for constructing solutions in graphs with small treewidth
