This paper presents a linear time self-stabilizing algorithm for detecting the set of fundamental cycles on an undirected connected graph modelling asynchronous distributed system.The previous known algorithm has O(n^2) time complexity, whereas we prove that this one stabilizesafter O(n) moves. The distributed adversarial scheduler is considered. Both algorithms assume that the depth-search spanning tree of the graph is given. The output is given in a distributed manner asa state of variables in the nodes.
In this paper we present some modification of the Blair and Manne algorithm for finding the center of a tree network in the distributed, self-stabilizing environment. Their algorithm finds n/2 -separator of a tree. Our algorithm finds weighted centroid, which is direct generalization of the former one for tree networks with positive weights on nodes. Time complexity of both algorithms is O(n2), where n is the number of nodes in the network.
W artykule podano algorytm rozproszonego, samostabilizującego się kolorowania grafów. Rozważamy spójny system niezależnych, asynchronicznych węzłów, z których każdy posiada tylko i wyłącznie lokalną wiedzę o systemie. Bez względu na stan początkowy system powinien osiągnąć pożądany stan globalny, wykonując w każdym z węzłów algorytm dany w postaci zbioru reguł. Zgodnie z naszą wiedzą przedstawiony algorytm jest pierwszym samostabilizującym algorytmem dokładnego kolorowania grafów dwudzielnych, działającym w wielomianowej liczbie ruchów.
EN
In the paper a distributed self-stabilizing algorithm for graph coloring is given. We consider a connected system of autonomous asynchronous nodes, each of which has only local information about the system. Regardless of the initial state, the system must achieve a desirable global state by executing a set of rules assigned to each node. Our method based on spanning trees is applied to give the first (to our knowledge) self-stabilizing algorithms working in a polynomial number of moves, which color bipartite graphs with exactly two colors.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.