On connected dominating sets of restricted diameter Academic Article

abstract

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

authors

• Butenko, Sergiy

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

publisher

• Elsevier  Publisher

published in

• European Journal of Operational Research  Journal

Digital Object Identifier (DOI)

• 10.1016/j.ejor.2013.11.036

start page

• 410

end page

• 418

volume

• 236

issue

• 2

URL

• http://dx.doi.org/10.1016/j.ejor.2013.11.036