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

DOI10.4230/LIPICS.ICALP.2017.57zbMATH Open1441.68185OpenAlexW2962770805MaRDI QIDQ5111388FDOQ5111388

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

Publication date: 27 May 2020

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

Recommendations

• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Uniform kernelization complexity of hitting forbidden minors
• Linear kernels and single-exponential algorithms via protrusion decompositions
• Linear kernels and single-exponential algorithms via protrusion decompositions
• Hitting forbidden minors: approximation and kernelization

zbMATH Keywords

approximationkernelizationimmersionprotrusiontree-cut width

Mathematics Subject Classification ID

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

Cited In (11)

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

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)