Efficient Algorithms for Topology Control Problem With Routing Cost Constraints in Wireless Networks
Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named ? Minimum rOuting Cost CDS (?-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, the authors prove that construction of a minimum ?-MOC-CDS is NP-hard in a general graph and they propose a heuristic algorithm for construction of ?-MOC-CDS.