Geodesic
A Linear Kernel for Planar Total Dominating Set
Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1.

Voir la notice de l'article provenant de la source Episciences

A total dominating set of a graph $G=(V,E)$ is a subset $D \subseteq V$ such that every vertex in $V$ is adjacent to some vertex in $D$. Finding a total dominating set of minimum size is NP-hard on planar graphs and W[2]-complete on general graphs when parameterized by the solution size. By the meta-theorem of Bodlaender et al. [J. ACM, 2016], there exists a linear kernel for Total Dominating Set on graphs of bounded genus. Nevertheless, it is not clear how such a kernel can be effectively constructed, and how to obtain explicit reduction rules with reasonably small constants. Following the approach of Alber et al. [J. ACM, 2004], we provide an explicit kernel for Total Dominating Set on planar graphs with at most $410k$ vertices, where $k$ is the size of the solution. This result complements several known constructive linear kernels on planar graphs for other domination problems such as Dominating Set, Edge Dominating Set, Efficient Dominating Set, Connected Dominating Set, or Red-Blue Dominating Set. 
@article{DMTCS_2018_20_1_a13,
     author = {Garnero, Valentin and Sau, Ignasi},
     title = {A {Linear} {Kernel} for {Planar} {Total} {Dominating} {Set}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2018},
     doi = {10.23638/DMTCS-20-1-14},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-14/}
}
TY  - JOUR
AU  - Garnero, Valentin
AU  - Sau, Ignasi
TI  - A Linear Kernel for Planar Total Dominating Set
JO  - Discrete mathematics & theoretical computer science
PY  - 2018
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-14/
DO  - 10.23638/DMTCS-20-1-14
LA  - en
ID  - DMTCS_2018_20_1_a13
ER  - 
%0 Journal Article
%A Garnero, Valentin
%A Sau, Ignasi
%T A Linear Kernel for Planar Total Dominating Set
%J Discrete mathematics & theoretical computer science
%D 2018
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-14/
%R 10.23638/DMTCS-20-1-14
%G en
%F DMTCS_2018_20_1_a13
Garnero, Valentin; Sau, Ignasi. A Linear Kernel for Planar Total Dominating Set. Discrete mathematics & theoretical computer science, Tome 20 (2018) no. 1. doi : 10.23638/DMTCS-20-1-14. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-20-1-14/

Cité par Sources :