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

• Autorzy: Bielak H. , Pańczyk M.

Identyfikatory

DOI

10.2478/v10065-012-0038-7

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

self-stabilizing algorithm; fundamental cycles; graph; DFS spanning tree

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2013
• Tom: Vol. 13, no. 1
• Strony: 7--10
• Opis fizyczny: Bibliogr. 7 poz., rys.

Twórcy

autor

Bielak H.

• Institute of Mathematics, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

autor

Pańczyk M.

• Institute of Computer Science, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

Bibliografia

• [1] Dijkstra E. W., Self-stabilizing in spite of distributed control, Communications of the ACM 17 (1974): 643.
• [2] Schneider M., Self-Stabilization, ACM Computing Surveys 25(1) (1993).
• [3] Dolev S., Self-stabilization, The MIT Press, 2000.
• [4] Harary F., Graph Theory, Addison-Wesley, 1972.
• [5] Chaudhuri P., A Self-Stabilizing Algorithm for Detecting Fundamental Cycles in a Graph, Journal of Computer and System Sciences 59 (1999): 84.
• [6] Collin Z., Dolev S., Self-stabilizing depth-first search, Information Processing Letters 49 (1994): 297.
• [7] Arora A., Gouda M. G., Closure and convergence: A foundation for fault-tolerant computing, Proceedings of the 22nd International Conference on Fault-Tolerant Computing Systems (1992).