Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs

DOI10.1007/978-3-540-73545-8_39zbMath1206.05073OpenAlexW2191175579MaRDI QIDQ3608864

Noga Alon, Shai Gutner

Publication date: 6 March 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73545-8_39

zbMATH Keywords

dominating set problemfixed-parameter tractable algorithmsH-minor-free graphsdegenerated graphsfinding an induced cycle

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (7)

Parameterized Complexity for Domination Problems on Degenerate Graphs ⋮ Parameterized complexity of generalized domination problems ⋮ Unnamed Item ⋮ The parameterized complexity of editing graphs for bounded degeneracy ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ Parameterized Algorithms for Generalized Domination

This page was built for publication: Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs