(6+epsilon)-Approximation for Minimum Weight Dominating Set in Unit Disk Graphs.
Xiaofeng GaoYaochun HuangZhao ZhangWeili WuPublished in: COCOON (2008)
Keyphrases
- minimum weight
- dominating set
- connected dominating set
- spanning tree
- maximum cardinality
- weighted graph
- bipartite graph
- facility location problem
- approximation algorithms
- minimum spanning tree
- randomized algorithm
- planar graphs
- minimum cost
- greedy heuristic
- edge weights
- facility location
- data objects
- graph theory
- undirected graph
- lower bound
- graph structure
- worst case
- greedy algorithm
- special case
- metaheuristic
- relational databases