## 1 Introduction  
Wireless sensor networks (WSNs) have received increasing attention in the last decade due to their potential applications in various fields such as environmental monitoring, medical and health applications, security surveillance and emergency operations [1]. They are generally composed of a rather large number of small devices, called sensors, with a limited low-power supply that depletes rather quickly. The lifetime of a sensor device (in hours) is generally calculated by dividing the battery capacity (in Watt hours) by the average power drain (in Watts). However, as the energy consumption also depends on other factors--such as, for example, the operating temperature--the estimation of the lifetime of a sensor node is not trivial [2]. One of the most challenging issues in WSNs is extending the lifetime of the network while providing sufficient sensing coverage and communication reliability. The lifetime of a network is defined as the time (duration) in which the network is fully functional with respect to the tasks that have to be fulfilled, that is, the time duration in which the overall sensing coverage is maintained. Therefore, WSN lifetime significantly depends on the energy consumption of sensors in the context of limited energy availability. Examples of real-world applications for maximizing sensor network lifetime can be found in [3] (human activity monitoring), [4] (smart agriculture monitoring), [5] (road traffic monitoring), and [6] (structural health monitoring). According to [7], power saving strategies can usually be classified under one of the following mechanisms:  
* Sleep-wake cycling (also called duty cycling): Sensors switch between active and sleep mode. * Power control by adjusting the transmission range of wireless nodes. Energy efficient routing, and data gathering. * Reducing the amount of transmitted data and avoiding useless activity. This study focuses on the first possibility, in the following way. The problem of extending (prolonging) WSN lifetime is addressed by organizing the sensors into a number of disjoint subsets that are activated successively. We require that each of these subsets is a dominating set of the communication graph defined by a sensor network. Note that, given the locations of the sensors, the communication graph is obtained by joining two sensors with an edge in case they can communicate with each other via their wireless antennas. The requirement of a subset of sensors being a dominating set is introduced such that each subset of nodes is able to cover the whole coverage area. The maximization of network lifetime has been studied in the literature from different perspectives. Most of them addressed the problem either via the set K-cover problem (also known as the target coverage problem) or as the domatic partition problem (also known as the maximum disjoint dominating sets problem). [PERSON] and [PERSON] [8] were the first ones to model the problem as a set K-cover problem and proved its NP-hardness using a polynomial time transformation from the minimum cover problem. The set K-cover problem is defined over a bipartite graph of two node sets (sensors and targets) with the aim to partition the sensors into a maximum number of disjoint sets (covers) over all targets. These sensor covers are then activated one after the other to effectively extend the WSN lifetime. The sensors of an active cover are able to monitor the entire set of targets. Due to the hardness of the problem, a variety of approximate algorithms have been devised, also for different variants of the problem. Examples include a greedy heuristic [8], memetic algorithms [9; 10; 11], cuckoo search [12] and a genetic algorithm [13]. As mentioned before, the maximization of the lifetime of WSNs is often approached through the domatic partition problem in which the goal is to find a partition of the nodes of a given network--represented as a simple, undirected graph--into a maximum number of disjoint dominating sets.