Explicit Linear Kernels via Dynamic Programming

DOI10.1137/140968975zbMath1323.05119arXiv1312.6585OpenAlexW2196420389MaRDI QIDQ3195132

Ignasi Sau, Dimitrios M. Thilikos, Christophe Paul, Valentin Garnero

Publication date: 21 October 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.6585

zbMATH Keywords

dynamic programmingparameterized complexitygraph minorslinear kernelsprotrusion replacement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Density (toughness, etc.) (05C42)

Related Items (11)

A Retrospective on (Meta) Kernelization ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Explicit linear kernels for packing problems ⋮ A linear kernel for planar red-blue dominating set ⋮ Editing to a planar graph of given degrees ⋮ Unnamed Item ⋮ Bidimensionality and Kernels ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs

This page was built for publication: Explicit Linear Kernels via Dynamic Programming