Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2013

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.

Domains

Discrete Mathematics [cs.DM]
Fichier principal
Vignette du fichier
13.pdf (819.12 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dimitrios Thilikos  : Connect in order to contact the contributor

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

Submitted on : Wednesday, January 18, 2017-8:41:06 PM

Last modification on : Friday, March 24, 2023-2:53:03 PM

Long-term archiving on : Wednesday, April 19, 2017-3:50:22 PM

Download

Dates and versions

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

Licence

Attribution - NoDerivatives

Identifiers

Cite

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ALGCO LIRMM TDS-MACS MIPS UNIV-MONTPELLIER
493 View
186 Download

Altmetric

Share

More