<?xml version="1.0" encoding="UTF-8"?> <article key="pdf/2907" mdate="2012-08-22 00:00:00"> <author>S. Balaji and N. Revathi</author> <title>An Efficient Heuristic for the Minimum Connected Dominating Set Problem on Ad Hoc Wireless Networks</title> <pages>1003 - 1009</pages> <year>2012</year> <volume>6</volume> <number>8</number> <journal>International Journal of Mathematical and Computational Sciences</journal> <ee>https://publications.waset.org/pdf/2907</ee> <url>https://publications.waset.org/vol/68</url> <publisher>World Academy of Science, Engineering and Technology</publisher> <abstract>Connected dominating set (CDS) problem in unit disk graph has signi&amp;pound;cant impact on an ef&amp;pound;cient design of routing protocols in wireless sensor networks, where the searching space for a route is reduced to nodes in the set. A set is dominating if all the nodes in the system are either in the set or neighbors of nodes in the set. In this paper, a simple and ef&amp;pound;cient heuristic method is proposed for &amp;pound;nding a minimum connected dominating set (MCDS) in ad hoc wireless networks based on the new parameter support of vertices. With this parameter the proposed heuristic approach effectively &amp;pound;nds the MCDS of a graph. Extensive computational experiments show that the proposed approach outperforms the recently proposed heuristics found in the literature for the MCD</abstract> <index>Open Science Index 68, 2012</index> </article>