Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2013

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

Résumé

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.

Domaines

Mathématique discrète [cs.DM]
Fichier principal
Vignette du fichier
13.pdf (819.12 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dimitrios Thilikos  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804758

Soumis le : mercredi 18 janvier 2017-20:41:06

Dernière modification le : vendredi 24 mars 2023-14:53:03

Archivage à long terme le : mercredi 19 avril 2017-15:50:22

Télécharger pour visualiser

Dates et versions

lirmm-00804758 , version 1 (18-01-2017)

Licence

Paternité - Pas de modifications

Identifiants

Citer

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. STACS: Symposium on Theoretical Aspects of Computer Science, Feb 2013, Kiel, Germany. pp.92-103, ⟨10.4230/LIPIcs.STACS.2013.92⟩. ⟨lirmm-00804758⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER
492 Consultations
186 Téléchargements

Altmetric

Partager

More