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 problem, a generalization of the classical minimum Vertex Cover problem, which allows to obtain a connected backbone. Recently, DelbotLP13 proposed a new centralized algorithm with a constant approximation ratio of @math 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.
From a self-stabilizing point of view, Kiniwa @cite_34 proposed the first self-stabilizing algorithm for this problem which constructs a 2-approximate vertex cover in general networks with unique nodes identifier and under a fair distributed daemon. This algorithm is based on the construction of a maximal matching which allows to obtain a 2-approximation vertex cover by selecting the extremities of the matching edges. Turau @cite_0 considered the same problem in anonymous networks and gave an 3-approximation algorithm under a distributed daemon. Since it is impossible to construct a maximal matching in an anonymous network, this algorithm establishes first a bicolored graph of the network allowing then to construct a maximal matching to obtain a vertex cover. Turau @cite_47 designed a self-stabilizing vertex cover algorithm with approximation ratio of 2 in anonymous networks under an unfair distributed daemon. This algorithm uses the algorithm in @cite_0 executed several times on parts of the graph to improve the quality of the constructed solution.
@cite_0 @cite_47 @cite_34
2110600065 1855768119 2064150382 1981311956
The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from O(n^2) and O(@dm) to O(m) where n is the number of processes, m is the number of edges, and @d is the maximum degree in the graph. A vertex cover of a graph is a subset of vertices such that each edge has at least one endpoint in the subset. Determining the minimum vertex cover is a well-known NP-complete problem in a sequential setting. Several techniques, e.g., depth-first search, a local ratio theorem, and semidefinite relaxation, have given good approximation algorithms. However, some of them cannot be applied to a distributed setting, in particular self-stabilizing algorithms. Thus only a 2-approximation solution based on a self-stabilizing maximal matching has been obviously known until now. In this paper we propose a new self-stabilizing vertex cover algorithm that achieves (2–1 Δ)-approximation ratio, where Δ is the maximum degree of a given network. We first introduce a sequential (2–1 Δ)-approximation algorithm that uses a maximal matching with the high-degree-first order of vertices. Then we present a self-stabilizing algorithm based on the same idea, and show that the output of the algorithm is the same as that of the sequential one. This paper presents a deterministic self-stabilizing algorithm that approximates a minimum vertex cover in anonymous networks with ratio 2 using the distributed scheduler and the link-register model with composite atomicity. No algorithm with a better approximation ratio can exist. The algorithm stabilizes in O(min n, Δ2, Δ log3 n ) rounds and requires O(Δ) memory per node. Abstract The non-computability of many distributed tasks in anonymous networks is well known. This paper presents a deterministic self-stabilizing algorithm to compute a ( 3 − 2 Δ + 1 ) -approximation of a minimum vertex cover in anonymous networks. The algorithm operates under the distributed unfair scheduler, stabilizes after O ( n + m ) moves respectively O ( Δ ) rounds, and requires O ( log n ) storage per node. Recovery from a single fault is reached within a constant time and the contamination number is O ( Δ ) . For trees the algorithm computes a 2 -approximation of a minimum vertex cover.