Linear kernels for edge deletion problems to immersion-closed graph classes

DOI10.4230/LIPICS.ICALP.2017.57MaRDI QIDQ5111388zbMATH OpenOpenAlexFDO

Authors Archontia C. Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, Marcin Wrochna

Publication date 27 May 2020

Full work available at URL https://doi.org/10.4230/lipics.icalp.2017.57

zbMATH Keywords

approximationimmersionkernelizationprotrusiontree-cut width

Mathematics Subject Classification ID

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

Recommendations

• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Hitting forbidden minors: approximation and kernelization

Cited in

(11)

• Cutwidth: obstructions and algorithmic aspects
• A Menger-like property of tree-cut width
• Partitioning a graph into small pieces with applications to path transversal
• The power of cut-based parameters for computing edge-disjoint paths
• Bidimensionality and kernels
• A Retrospective on (Meta) Kernelization
• Modification to Planarity is Fixed Parameter Tractable
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Faster parameterized algorithms for modification problems to minor-closed classes

This page was built for publication: Linear kernels for edge deletion problems to immersion-closed graph classes

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