Linear kernels and single-exponential algorithms via protrusion decompositions

DOI10.1145/2797140MaRDI QIDQ6829646zbMATH OpenFDO

Authors Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, Ignasi Sau, Somnath Sikdar

Publication date 30 October 2018

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2797140

zbMATH Keywords

algorithmic meta-theoremsgraph minorshitting minorsparameterized complexitysparse graphs

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(7)

• An FPT-algorithm for recognizing k-apices of minor-closed graph classes
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Compound logics for modification problems
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Graph modification of bounded size to minor-closed classes as fast as vertex deletion
• Enumeration kernels for vertex cover and feedback vertex set
• Quadratic kernel for cliques or trees vertex deletion

This page was built for publication: Linear kernels and single-exponential algorithms via protrusion decompositions

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