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

Acte de colloque

Open Access

Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh et Dimitrios M. Thilikos

30th Symposium on Theoretical Aspects of Computer Science, Vol.LIPIcs(20), pp.92-103

STACS: Symposium on Theoretical Aspects of Computer Science (Kiel, Germany, 27/02/2013–02/03/2013)

18/02/2013

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.

url

Find in HALAfficher

1 Consultations de la notice

Titre: Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs
Créateurs - sans rôle: Fedor V. Fomin - Department of Informatics [Bergen]
Daniel Lokshtanov - Department of Informatics [Bergen]
Saket Saurabh - Institute of Mathematical Sciences
Dimitrios M. Thilikos - Department of Mathematics [Athens]
Détails de publication: 30th Symposium on Theoretical Aspects of Computer Science, Vol.LIPIcs(20), pp.92-103
Colloque: STACS: Symposium on Theoretical Aspects of Computer Science (Kiel, Germany, 27/02/2013–02/03/2013)
Identifiants: 9947427809311
Unité académique: Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier - LIRMM
Langue: English
Type de ressource: Conference proceeding
Champs locaux: lirmm-00804758