On connected dominating sets of restricted diameter |
| |
Authors: | Austin Buchanan Je Sang Sung Vladimir Boginski Sergiy Butenko |
| |
Institution: | 1. Texas A&M University, Department of Industrial and Systems Engineering College Station, TX 77843-3131, United States;2. University of Florida, Department of Industrial and Systems Engineering Gainesville, FL 32611-6595, United States |
| |
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. |
| |
Keywords: | Connected dominating set Bounded diameter subgraphs s-Club Clique Wireless networks |
本文献已被 ScienceDirect 等数据库收录! |
|