Lossy Kernels for Hitting Subgraphs

DOI10.4230/LIPICS.MFCS.2017.67zbMATH Open1441.68175OpenAlexW2773937539MaRDI QIDQ5111284FDOQ5111284

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/

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

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)

Cites Work

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

Cited In (8)

• 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
• Title not available (Why is that?)
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Lossy kernelization

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)