Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks.
Traian Marius TrutaAlina CampanMatthew BeckerichPublished in: Int. J. Serv. Sci. Manag. Eng. Technol. (2018)
Keyphrases
- approximation algorithms
- social networks
- minimum cost
- constant factor
- np hard
- vertex cover
- special case
- worst case
- network design problem
- set cover
- primal dual
- randomized algorithms
- approximation ratio
- strongly np hard
- facility location problem
- np hardness
- undirected graph
- open shop
- lower bound
- disjoint paths
- greedy algorithm
- upper bound
- optimal solution