Lossy Kernels for Hitting Subgraphs

DOI10.4230/LIPICS.MFCS.2017.67MaRDI QIDQ5111284zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Danny Hermelin, M. S. Ramanujan

Publication date 26 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8095/pdf/LIPIcs-MFCS-2017-67.pdf/

zbMATH Keywords

graph theoryparameterized algorithmslossy kernelization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernelization
• Kernelization Algorithms for d-Hitting Set Problems

Cites work

• scientific article; zbMATH DE number 1263241 (Why is no real title available?)
• (Meta) kernelization
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Fundamentals of parameterized complexity
• Incompressibility through Colors and IDs
• Intersection Theorems for Systems of Sets
• Kernelization -- preprocessing with a guarantee
• Kernelization and Sparseness: the case of Dominating Set
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Linearity of grid minors in treewidth with applications through bidimensionality
• Lossy kernelization
• Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
• Parameterized algorithms
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Recent developments in kernelization: a survey
• Steiner tree approximation via iterative randomized rounding
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The steiner problem in graphs

Cited in

(9)

• Lossy kernels for connected dominating set on sparse graphs
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• Approximate Turing Kernelization for Problems Parameterized by Treewidth
• Lossy kernels for connected dominating set on sparse graphs
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Kernelization of counting problems
• Lossy kernelization
• An approximate kernel for connected feedback vertex set

This page was built for publication: Lossy Kernels for Hitting Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111284)