A linear kernel for planar total dominating set

MaRDI QIDQ4560237zbMATH OpenFDO

Authors Valentin Garnero, Ignasi Sau

Publication date 10 December 2018

Full work available at URL https://arxiv.org/abs/1211.0978, https://dmtcs.episciences.org/4487/pdf

zbMATH Keywords

linear kernelsparameterized complexityplanar graphstotal domination

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Simpler linear-time kernelization for planar dominating set
• A linear kernel for a planar connected dominating set
• Linear Kernel for Planar Connected Dominating Set
• A linear kernel for planar red-blue dominating set

Cited in

(6)

• On some domination colorings of graphs
• Linear-time computation of a linear problem kernel for dominating set on planar graphs
• Linear Kernel for Planar Connected Dominating Set
• Kernelization and Sparseness: the case of Dominating Set
• A linear kernel for planar red-blue dominating set
• Total domination and open packing in some subclasses of bipartite graphs

This page was built for publication: A linear kernel for planar total dominating set

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