HAL TEI export of lirmm-00846771 CCSD CC0 1.0 - Universal

HAL API Platform

 A linear kernel for planar red-blue dominating set Valentin Garnero f0647c612978d1b6c082334db9c9c875 univ-grenoble-alpes.fr v-garnero 9984 23573-9984 https://www.idref.fr/227138333 https://viaf.org/viaf/110152864162004821852 Ignasi Sau 0cf496e357a0f831666492fefcf2203b gmail.com ignasi-sau 7331 2727823-7331 https://orcid.org/0000-0002-8981-9287 https://www.idref.fr/137767420 Dimitrios M. Thilikos b12f47ffd4c78cdb273f5b91bb335a0e thilikos.Info dimitrios-m-thilikos 178742 17649-178742 https://orcid.org/0000-0003-0470-1800 https://www.idref.fr/149337078 Dimitrios Thilikos b12f47ffd4c78cdb273f5b91bb335a0e thilikos.info 2013-07-19 19:53:14 2013-05-03 2025-08-13 03:14:21 2013-08-20 16:51:12 2013-05-21 2013-07-19 contributor Dimitrios Thilikos b12f47ffd4c78cdb273f5b91bb335a0e thilikos.info CCSD lirmm-00846771 https://hal-lirmm.ccsd.cnrs.fr/lirmm-00846771 garnero:lirmm-00846771 <i>CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization</i>, May 2013, Enschede, Netherlands. pp.117-120 CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization, May 2013, Enschede, Netherlands. pp.117-120 HAL Authorization CNRS - Centre national de la recherche scientifique Algorithmes, Graphes et Combinatoire Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier Réseau de recherche en Théorie des Systèmes Distribués, Modélisation, Analyse et Contrôle des Systèmes Mathématiques, Informatique, Physique et Systèmes Université de Montpellier Université de Montpellier (2015-2021) International No No Yes Yes A linear kernel for planar red-blue dominating set Valentin Garnero f0647c612978d1b6c082334db9c9c875 univ-grenoble-alpes.fr v-garnero 9984 23573-9984 https://www.idref.fr/227138333 https://viaf.org/viaf/110152864162004821852 Ignasi Sau 0cf496e357a0f831666492fefcf2203b gmail.com ignasi-sau 7331 2727823-7331 https://orcid.org/0000-0002-8981-9287 https://www.idref.fr/137767420 Dimitrios M. Thilikos b12f47ffd4c78cdb273f5b91bb335a0e thilikos.Info dimitrios-m-thilikos 178742 17649-178742 https://orcid.org/0000-0003-0470-1800 https://www.idref.fr/149337078 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization CTW: Cologne-Twente Workshop on Graphs and Combinatorial Optimization 2013-05-21 2013-05-23 Enschede Netherlands 117-120 2013-05-22 1408.6388 http://wwwhome.math.utwente.nl/~ctw/index.php?page=home English parameterized complexity planar graphs linear kernels domination Computer Science [cs]/Discrete Mathematics [cs.DM] Computer Science [cs]/Data Structures and Algorithms [cs.DS] Conference papers Conference papers Conference papers

In the Red-Blue Dominating Set problem, we are given a bipartite graph $G = (V_B \cup V_R,E)$ and an integer $k$, and asked whether $G$ has a subset $D \subseteq V_B$ of at most $k$'blue' vertices such that each 'red' vertex from $V_R$ is adjacent to a vertex in $D$. We provide the first explicit linear kernel for this problem on planar graphs.

 Algorithmes, Graphes et Combinatoire ALGCO 2021-12-31
LIRMM, 161 rue Ada, 34000 Montpellier
https://www.lirmm.fr/equipes/ALGCO/ Department of Mathematics [Athens]
Panepistimioupolis, GR-157 84, Athens
http://noether.math.uoa.gr/ 139590827 0000000405990488 199111950H https://ror.org/013yean28 Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier LIRMM 1995-01-01 2021-12-31
161 rue Ada - 34095 Montpellier
https://www.lirmm.fr 0000000120970141 https://ror.org/051escj72 Université de Montpellier UM 2021-12-31
163 rue Auguste Broussonnet - 34090 Montpellier
http://www.umontpellier.fr/ 02636817X 0000000122597504 https://ror.org/02feahw73 Centre National de la Recherche Scientifique CNRS 1939-10-19
https://www.cnrs.fr/ https://ror.org/04gnjpq42 National and Kapodistrian University of Athens NKUA 1837-04-14
Athens 157 72
https://en.uoa.gr/