Explicit linear kernels via dynamic programming

DOI10.4230/LIPICS.STACS.2014.312MaRDI QIDQ2965494zbMATH OpenFDO

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

Publication date 3 March 2017

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2014.312

zbMATH Keywords

dynamic programminggraph minorslinear kernelsparameterized complexityprotrusion replacement

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Recommendations

• Explicit linear kernels via dynamic programming
• Bidimensionality and kernels
• Explicit linear kernels for packing problems
• Kernels for (connected) dominating set on graphs with excluded topological minors
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs

Cited in

(7)

• Explicit linear kernels for packing problems
• Changes in dense linear algebra kernels: decades-long perspective
• Kernelization using structural parameters on sparse graph classes
• Editing to a planar graph of given degrees
• Explicit linear kernels via dynamic programming
• Kernels for (connected) dominating set on graphs with excluded topological minors
• scientific article; zbMATH DE number 5026764 (Why is no real title available?)

This page was built for publication: Explicit linear kernels via dynamic programming

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