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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00804758
Contributor : Dimitrios M. Thilikos <>
Submitted on : Wednesday, January 18, 2017 - 8:41:06 PM
Last modification on : Thursday, November 15, 2018 - 8:16:28 PM
Long-term archiving on : Wednesday, April 19, 2017 - 3:50:22 PM

File

13.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

560

Files downloads

261