A performance study of some approximation algorithms for minimum dominating set in a graph.
Jonathan S. LiRohan PotruFarhad ShahrokhiPublished in: CoRR (2020)
Keyphrases
- dominating set
- approximation algorithms
- facility location problem
- connected dominating set
- np hard
- constant factor
- minimum cost
- special case
- worst case
- facility location
- approximation ratio
- approximation schemes
- set cover
- undirected graph
- linear programming
- polynomial time approximation
- vertex cover
- disjoint paths
- search algorithm