Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
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.
Fichier principal
Vignette du fichier
13.pdf (819.12 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

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⟩
482 View
166 Download

Altmetric

Share

Gmail Facebook X LinkedIn More