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

• Autorzy: Kosowski A. , Kuszner Ł.

Warianty tytułu

EN

A self-stabilizing algorithm for coloring bipartite graphs and cacti

• Konferencja: XV Krajowa Konferencja Automatyzacji Procesów Dyskretnych, Zakopane, 20-23 września 2006r.
• Języki publikacji: PL

Abstrakty

PL

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.

Słowa kluczowe

PL

graf dwudzielny; kaktus; kolorowanie grafów; algorytm kolorowania; algorytm samostabilizujący

EN

bipartite graph; cacti; graph coloring; algorithm for coloring; self-stabilizing algorithm

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2006
• Tom: z. 143
• Strony: 75--81
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Kosowski A.

autor

Kuszner Ł.

• Katedra Algorytmów i Modelowania Systemów Politechniki Gdańskiej, 80-952 Gdańsk Wrzeszcz, ul. Gabriela Narutowicza 11/12, tel.: [phone],

Bibliografia

• 1. Battiti R., Bertossi A.A., Bonuccelli MA.: Assigning codes in wireless networks. Wireless Networks 5, 1999, p. 195-209.
• 2. Dijkstra E.W.: Self-stabilizing systems in spite of distributed control. Communications of the ACM 17, 1974, p. 643-644.
• 3. Ghosh S., Karaata M.H.: A self-stabilizing algorithm for coloring planar graphs. Distributed Computing 7, 1993, p. 55-59.
• 4. Hedetniemi S.T., Jacobs D.P., Srimani P.K.: Linear time self-stabilizing colorings. Information Processing Letters 87, 2003, p. 251-255.
• 5. Johansson Ö.: Simple distributed Δ + 1 - coloring of graphs. Information Processing Letters 70, 1999, p. 229-232.
• 6. Kelsen P.: Neighborhood graphs and distributed (Δ + l)-coloring. Proc. SWAT LNCS 1097, 1996, p. 223-233.
• 7. Kosowski A., Kuszner Ł.: A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves. Proc. PPAM LNCS 3911, 2006, p. 75-82.
• 8. Kubale M. i inni: Graph Colorings, Contemporary Mathematics 352, AMS, 2004.
• 9. Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. Journal of Algorithms 20, 1996, p. 356-374.
• 10. Shamir E., Upfal E.: Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces. Journal of Algorithms 5, 1984, p. 488-501.
• 11. Sur S., Srimani P.K.: A self-stabilizing algorithm for coloring bipartite graphs. Information Sciences 69, 1993, p. 219-227.