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ć.