Meta-kernelization using well-structured modulators

DOI10.1016/j.dam.2017.09.018zbMath1396.68055arXiv1507.05544OpenAlexW2962845686MaRDI QIDQ2413976

Robert Ganian, Eduard Eiben, Stefan Szeider

Publication date: 17 September 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.05544

zbMATH Keywords

parameterized complexitystructural parameterskernelizationrank-widthsplit decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (2)

A Retrospective on (Meta) Kernelization ⋮ Measuring what matters: a hybrid approach to dynamic programming with treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Kernelization using structural parameters on sparse graph classes
• Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Kernel bounds for path and cycle problems
• Sparsity. Graphs, structures, and algorithms
• Solving MAX-\(r\)-SAT above a tight lower bound
• Elements of finite model theory.
• Meta-kernelization with structural parameters
• On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Linear time solvable optimization problems on graphs of bounded clique-width
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Approximating clique-width and branch-width
• (Meta) Kernelization
• Solving Problems on Graphs of High Rank-Width
• An algebraic theory of graph reduction
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• Kernelization Lower Bounds by Cross-Composition
• Meta-kernelization using Well-structured Modulators
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• Bidimensionality and Geometric Graphs
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Meta-kernelization using well-structured modulators