Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: self-stabilizing algorithm

Sortuj według:

Ogranicz wyniki do:

A self-stabilizing algorithm for detecting fundamental cycles in a graph with DFS spanning tree given

Bielak H., Pańczyk M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2013

Vol. 13, no. 1

7--10

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.

A self–stabilizing algorithm for finding weighted centroid in trees

Bielak H., Pańczyk M.

Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica

2012

Vol. 12, no. 2

27--37

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.

Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

Kosowski A., Kuszner Ł.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2006

z. 143

75-81

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.

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.