Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs

Abstract : We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph H as a topological minor.
Type de document :
Communication dans un congrès
STAC: Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. 30th Symposium on Theoretical Aspects of Computer Science, 20, pp.92-103, 2013, 〈http://www.stacs2013.uni-kiel.de〉. 〈10.4230/LIPIcs.STACS.2013.92〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804758
Contributeur : Dimitrios M. Thilikos <>
Soumis le : mercredi 18 janvier 2017 - 20:41:06
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mercredi 19 avril 2017 - 15:50:22

Fichier

13.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas de modifications 4.0 International License

Identifiants

Collections

Citation

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. STAC: Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. 30th Symposium on Theoretical Aspects of Computer Science, 20, pp.92-103, 2013, 〈http://www.stacs2013.uni-kiel.de〉. 〈10.4230/LIPIcs.STACS.2013.92〉. 〈lirmm-00804758〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

101