An Approximation Algorithm for Vertex Cover Problem

. An emerging problem in wireless sensors network is the need to increase the network life time. In a network with two power modes, this goal can be achieved by choosing the minimum number of sensors that have high power mode (long range radio) in the service area. The vertex cover assist in organizing clusters and determine the cluster head to save power and ensure that all sensors in the network are accessible by the cluster heads, The minimum (optimal) number of vertices (sensors) problem is NP-Complete. Therefore, a near-optimal solution to the problem can be obtained by an approximation algorithm that solves the problem in polynomial time. In this paper, we propose a new algorithm for minimizing the number of node that represents the wireless sensor with high transition power, thus we minimize the power consumption of the wireless sensor network and prolong the network life time.