|
 
|
[DLR14] Self-stabilizing Algorithms for Connected Vertex Cover and Clique Decomposition Problems
Conférence Internationale avec comité de lecture : 18th International Conference on Principles of Distributed Systems, December 2014, Vol. 8878, pp.307--322, Series Lecture Notes in Computer Science, (DOI: 10.1007/978-3-319-14472-6_21)Mots clés: Distributed algorithms, Self-stabilization, Connected Vertex Cover, Connected Minimal Clique Partition
Résumé:
In many wireless networks, there is no fixed physical backbone nor centralized network management. The nodes of such a network have to self-organize in order to maintain a virtual backbone used to route messages. Moreover, any node of the network can be a priori at the origin of a malicious attack. Thus, in one hand the backbone must be fault-tolerant and in other hand it can be useful to monitor all network communications to identify an attack as soon as possible. We are interested in the minimum Connected Vertex Cover problem, a generalization of the classical minimum Vertex Cover problem, which allows to obtain a connected backbone. Recently, Delbot et al. [11] proposed a new centralized algorithm with a constant approximation ratio of 2 for this problem. In this paper, we propose a distributed and self-stabilizing version of their algorithm with the same approximation guarantee. To the best knowledge of the authors, it is the first distributed and fault-tolerant algorithm for this problem. The approach followed to solve the considered problem is based on the construction of a connected minimal clique partition. Therefore, we also design the first distributed self-stabilizing algorithm for this problem, which is of independent interest.
Equipe:
mim
BibTeX
| @inproceedings { | |||
| DLR14, | |||
| title | = | "{Self-stabilizing Algorithms for Connected Vertex Cover and Clique Decomposition Problems}", | |
| author | = | " F. Delbot and C. Laforest and S. Rovedakis ", | |
| booktitle | = | "{18th International Conference on Principles of Distributed Systems}", | |
| year | = | 2014, | |
| edition | = | "Springer", | |
| month | = | "December", | |
| series | = | "Lecture Notes in Computer Science", | |
| volume | = | 8878, | |
| pages | = | "307--322", | |
| doi | = | "10.1007/978-3-319-14472-6_21", | |
| } | |||
