Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6897403 | European Journal of Operational Research | 2014 | 9 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Austin Buchanan, Je Sang Sung, Vladimir Boginski, Sergiy Butenko,