In the self-stabilizing algorithmic paradigm for distributed computation, each node has only a local view of the system, yet in a finite amount of time, the system converges to a global state satisfying some desired p...
详细信息
In the self-stabilizing algorithmic paradigm for distributed computation, each node has only a local view of the system, yet in a finite amount of time, the system converges to a global state satisfying some desired property. In this paper, we present polynomial time self-stabilizing algorithms for finding a dominating bipartition, a maximal independent set, and a minimal dominating set in any graph. (C) 2003 Elsevier Ltd. All rights reserved.
This paper presents a self-stabilizing algorithm for mutual exclusion in asynchronous networks. The algorithm is token based and a binary tree network topology is used The algorithm is resilient to transient faults an...
详细信息
ISBN:
(纸本)1892512459
This paper presents a self-stabilizing algorithm for mutual exclusion in asynchronous networks. The algorithm is token based and a binary tree network topology is used The algorithm is resilient to transient faults and does not require initialization. It has been proved that the algorithm is correct and requires O(n) moves, where n is the number of nodes in the system.
This paper presents a self-stabilizing algorithm for the minimum-depth search (MDS) of a connected undirected graph on an asynchronous distributed or network model of computation. The algorithm produces a minimum-dept...
详细信息
This paper presents a self-stabilizing algorithm for the minimum-depth search (MDS) of a connected undirected graph on an asynchronous distributed or network model of computation. The algorithm produces a minimum-depth spanning tree (MDST) of the given graph in a distributed manner so that each node of the graph knows its depth and parent. The algorithm is resilient to transient faults and does not require initialization. It has been proved that the algorithm is correct and requires O(n(2)) time, where n is the number of nodes of the graph. (C) 1999 Elsevier Science Inc. All rights reserved.
This paper presents a self-stabilizing algorithm that finds the bridge-connected components of a connected undirected graph on an asynchronous distributed or network model of computation. An edge of a graph is a bridg...
详细信息
This paper presents a self-stabilizing algorithm that finds the bridge-connected components of a connected undirected graph on an asynchronous distributed or network model of computation. An edge of a graph is a bridge if its removal disconnects the graph. The bridge-connected components problem consists of finding the maximal connected subgraphs (components) of the given graph such that none of the components contains a bridge. The output of the algorithm is available in a distributed manner in the sense that, upon termination of the algorithm, each node of the graph knows its component number: the component number is a representative node number which uniquely identifies a bridge-connected component. It has been proved that the algorithm is correct and requires O(n(2)) time if the depth-first search spanning tree of the graph is known, or else it requites O(n(2) + n . d . Delta) time, where n is the number of nodes, d is the graph diameter, and a is an upper bound on the degree of a node.
A self-stabilizing algorithm for detecting the articulation points of a connected undirected graph on an asynchronous distributed model of computation is proposed in this note. For a given graph if the deletion of a n...
详细信息
A self-stabilizing algorithm for detecting the articulation points of a connected undirected graph on an asynchronous distributed model of computation is proposed in this note. For a given graph if the deletion of a node splits the graph into two or more components then that node is called an articulation point. The algorithm is resilient to transient faults and does not require initialization. (C) 1999 Elsevier Science B.V. All rights reserved.
We propose a simple self-stabilizing distributed algorithm that maintains an arbitrary spanning tree in a connected graph. In proving the correctness of the algorithm, we develop a new technique without using a bounde...
详细信息
We propose a simple self-stabilizing distributed algorithm that maintains an arbitrary spanning tree in a connected graph. In proving the correctness of the algorithm, we develop a new technique without using a bounded function (which is customary for proving correctness of self-stabilizing algorithms);the new approach is simple and can be potentially applied to proving correctness of other self-stabilizing algorithms.
暂无评论