Stable Approximation Algorithms for Dominating Set and Independent Set.
Mark de BergArpan SadhukhanFrits C. R. SpieksmaPublished in: APPROX/RANDOM (2023)
Keyphrases
- approximation algorithms
- dominating set
- facility location problem
- independent set
- np hard
- connected dominating set
- special case
- worst case
- minimum cost
- maximum weight
- maximum independent set
- vertex cover
- randomized algorithms
- constant factor
- constant factor approximation
- disjoint paths
- approximation ratio
- computational complexity
- search algorithm
- branch and bound algorithm