On connected dominating sets of restricted diameter Academic Article uri icon


  • 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.

published proceedings

  • European Journal of Operational Research

author list (cited authors)

  • Buchanan, A., Sung, J. S., Boginski, V., & Butenko, S.

citation count

  • 13

complete list of authors

  • Buchanan, Austin||Sung, Je Sang||Boginski, Vladimir||Butenko, Sergiy

publication date

  • January 2014