Abstract
In this thesis, we give results on three algorithmical problems in graphs.First, we study the Distance-2 Broadcast Scheduling problem in wireless ad-hoc networks. We assume that time is discretized into slots. At each slot, all the communication events take place simultaneously. Given a network and a source node detaining a piece of information, distance-2 broadcast scheduling consists in scheduling the communication events to spread the information to every node within distance 2 of the source. The study is rather theoretical: we aim at establishing "good" bounds depending on the structure of the network. For instance, we give upper bounds on the number of slots sufficient to complete broadcast, or lower bounds on the number of nodes that can be informed in a limited number of slots. We refine those bounds in various classes of networks characterized by the structure of the underlying graph.We then tackle the Balanced Connected Subgraph problem: given a graph which vertices are colored either red or blue, find the largest connected subgraph containing as many red vertices as blue vertices. Our study focuses on the classification of the problem when restricted to "small" classes of graphs, namely bipartite cubic graphs, graphs of diameter three and bipartite graphs of diameter four. We show that the problem remains NP-complete in each of those classes. In addition, we prove it non-approximable within constant factor in the case of bipartite graphs of maximum degree four.Last, we give a novel approach to fault tolerance for extending lifetime of wireless sensor networks. These networks are used for a variety of applications including surveillance and monitoring. They consist of large amounts of autonomous devices with sensing capabilities deployed to monitor vast areas. Usually, these devices run on limited batteries and communicate wirelessly. Thus, numerous optimization problems have appeared. We study the problem of scheduling sensor activity in order to extend network lifetime. The goal is to ensure that at all time each target is monitored by at least one sensor, and the set of active sensors does relay the information to a specified communication base. We describe a new approach which addresses this problem with a fault-tolerant solution. We then validate our approach by simulation.