Lossy Kernels for Connected Dominating Set on Sparse Graphs

DOI10.1137/18M1172508zbMath1430.68195MaRDI QIDQ5234662

Sebastian Siebertz, Fahad Panolan, Amer E. Mouawad, Eduard Eiben, Mithilesh Kumar

Publication date: 30 September 2019

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

connected dominating set; parameterized complexity; sparse graph classes; lossy kernelization

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68Q27: Parameterized complexity, tractability and kernelization