Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems

DOI10.1137/1.9781611973402.123zbMath1423.68598arXiv1311.2309OpenAlexW1484268536MaRDI QIDQ5384085

Manish Purohit, Samir Khuller, Kanthi K. Sarpatwar

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1311.2309

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 (16)

An approximation algorithm for maximum weight budgeted connected set cover ⋮ Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ On maximum leaf trees and connections to connected maximum cut problems ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ Revisiting connected dominating sets: an almost optimal local information algorithm ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ Parameterized Dynamic Variants of Red-Blue Dominating Set ⋮ Selective harvesting over networks ⋮ Maximum rooted connected expansion ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ Approximation algorithms for connected maximum cut and related problems ⋮ Algorithm and complexity of the two disjoint connected dominating sets problem on trees

This page was built for publication: Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems