On connected dominating sets of restricted diameter
- Additional Document Info
- View All
A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than s leading to the concept of a dominating s-club. We prove that for any fixed positive integer s it is NP-complete to determine if a graph has a dominating s-club, even when the graph has diameter s+1. As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results. 2014 Elsevier B.V. All rights reserved.
European Journal of Operational Research
author list (cited authors)
Buchanan, A., Sung, J. S., Boginski, V., & Butenko, S.
complete list of authors
Buchanan, Austin||Sung, Je Sang||Boginski, Vladimir||Butenko, Sergiy