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 f...
详细信息
ISBN:
(纸本)9783540729181
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(delta m) to O(m) where n is the number of processes, m is the number of edges, and delta is the maximum degree in the graph. (C) 2008 Elsevier B.V. All rights reserved.
A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels axe equal or larger. Distributed algorithms that reach a legitimate state, starting ...
详细信息
A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels axe equal or larger. Distributed algorithms that reach a legitimate state, starting from any illegitimate state, are called self-stabilizing. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. [4] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. The motivation of k-forward numberings is to obtain new s-s graph coloring algorithms. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata [13], as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.
The problem of computing a matching in a graph involves creating pairs of neighboring nodes such that no node is paired more than once. Previous work on the matching problem has resulted in several self-stabilizing al...
详细信息
ISBN:
(纸本)9783540766261
The problem of computing a matching in a graph involves creating pairs of neighboring nodes such that no node is paired more than once. Previous work on the matching problem has resulted in several self-stabilizing algorithms for finding a maximal matching in an unweighted graph. In this paper we present the first self-stabilizing algorithm for the weighted matching problem. We show that the algorithm computes a 1/2-approximation to the optimal solution. The algorithm is simple and uses only a fixed number of variables per node. Stabilization is shown under various types of daemons.
The k-packing problem asks for a subset S of the nodes in a graph such that the distance between any pair of nodes in S is greater than k. This problem has applications to placing facilities in a network. In the curre...
详细信息
ISBN:
(纸本)3540490183
The k-packing problem asks for a subset S of the nodes in a graph such that the distance between any pair of nodes in S is greater than k. This problem has applications to placing facilities in a network. In the current paper we present a self-stabilizing algorithm for computing a maximal k-packing in a general graph. Our algorithm uses a constant number of variables per node. This improves the memory requirement compared to the previous most memory efficient algorithm [9] which used k variables per node. In addition the presented algorithm is very short and simple.
In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O(log(n)) bits per processor where n is the number of processors). O...
详细信息
In this paper, we present a self-stabilizing algorithm for finding cut-nodes and bridges in arbitrary rooted networks with a low memory requirement (O(log(n)) bits per processor where n is the number of processors). Our algorithm is silent and must be composed with a silent self-stabilizing algorithm computing a Depth-First Search (DFS) Spanning Tree of the network. So, in the paper, we will prove that the composition of our algorithm with any silent self-stabilizing DFS algorithm is self-stabilizing. Finally, we will show that our algorithm needs O(n(2)) moves to reach a terminal configuration once the DFS spanning tree is computed. Note that this time complexity is equivalent to the best proposed solutions.
Spanning trees help removing cycles and establishing short paths between a given node and the rest of the nodes in a network. In ad hoc mobile computing networks, however, transient node failures occur due to being ou...
详细信息
Spanning trees help removing cycles and establishing short paths between a given node and the rest of the nodes in a network. In ad hoc mobile computing networks, however, transient node failures occur due to being out of range or powered off. Therefore, we present a self-stabilized distributed algorithm based on homogeneous agents for constructing a random spanning tree. Our approach makes use of distributed random walks as a network traversal scheme, in order to handle dynamic topology changes in ad hoc wireless networks. Each random walk is represented by a mobile agent annexing a territory over the underlying network. These multiple random walks collapse into a final one that defines the random spanning tree. It will be shown that, compared to deterministically predetermined spanning trees, our algorithm is more resilient to transient failures that occur in ad hoc mobile networks. (C) 2003 Elsevier Science (USA). All rights reserved.
In this paper, we design a self-stabilizing algorithm which finds a a-center for a distributed system with a tree topology. Our algorithm is based on the algorithm in [1-3]. The latter enables us to find the center (o...
详细信息
In this paper, we design a self-stabilizing algorithm which finds a a-center for a distributed system with a tree topology. Our algorithm is based on the algorithm in [1-3]. The latter enables us to find the center (or centers) for the tree. If we sever the tree at the center (or centers), we obtain two subtrees. One of the major works in this paper is to show that if we pick a center from each subtree, the two picked centers will constitute a a-center for the original tree. With this in mind, we design our algorithm so that it is equipped with the ability of "sensing" the two subtrees and then finding a center in each of them. (C) 2000 Elsevier Science Ltd. All rights reserved.
A self-stabilizing algorithm for constructing breadth-first trees is proposed. Its self-stabilizing property is proven. A convincing and straightforward way to prove a system self-stabilizing is: First prove that the ...
详细信息
A self-stabilizing algorithm for constructing breadth-first trees is proposed. Its self-stabilizing property is proven. A convincing and straightforward way to prove a system self-stabilizing is: First prove that the system can always make a computation step as long as the system is not stabilized, and give a bounded function whose value decreases for each computation step. But in some cases, it may be hard or even unlikely to find such a bounded function. However, by transforming the original set of rules into another set of rules so that both sets of rules have the equivalent effect, it may become easier to find such a bounded function from the transformed rules. The provided proof adopts this concept.
暂无评论