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

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

Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Improved budgeted connected domination and budgeted edge-vertex domination

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Improved performance of the greedy algorithm for partial cover
Connected dominating set. Theory and applications
Clustering to minimize the maximum intercluster distance
Approximation algorithms for connected dominating sets
The budgeted maximum coverage problem
An analysis of the greedy algorithm for the submodular set covering problem
Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Distributed algorithms for connected domination in wireless networks
A primal-dual approximation algorithm for partial vertex cover: Making educated guesses
The polymatroid Steiner problems
A greedy approximation algorithm for the group Steiner problem
A threshold of ln n for approximating set cover
New Approximation Results for Resource Replication Problems
Covering Problems with Hard Capacities
Polylogarithmic inapproximability
Saving an epsilon
A robust maximum completion time measure for scheduling
Scheduling with Outliers
An analysis of approximations for maximizing submodular set functions—I
A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
Approximation algorithms for partial covering problems
Spanning Trees—Short or Small
Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination
Constant approximation for k-median and k-means with outliers via iterative rounding
Analytical approach to parallel repetition
Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
Analyzing the Optimal Neighborhood: Algorithms for Budgeted and Partial Connected Dominating Set Problems
Approximation of Partial Capacitated Vertex Cover
A tight bound on approximating arbitrary metrics by tree metrics

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