Approximation algorithms for connected dominating sets

DOI10.1007/3-540-61680-2_55zbMath1379.68352OpenAlexW2134003300MaRDI QIDQ4595486

Samir Khuller, Sudipto Guha

Publication date: 5 December 2017

Published in: Algorithms — ESA '96 (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/830

Mathematics Subject Classification ID

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

Related Items (6)

Leafy spanning \(k\)-forests ⋮ An exact algorithm for the maximum leaf spanning tree problem. ⋮ Approximation hardness of dominating set problems in bounded degree graphs ⋮ Algorithmic aspects of secure connected domination in graphs ⋮ The maximum-leaf spanning tree problem: Formulations and facets ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems

This page was built for publication: Approximation algorithms for connected dominating sets