A self–stabilizing algorithm for finding weighted centroid in trees

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

Identyfikatory

DOI

10.2478/v10065-012-0035-x

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

self-stabilizing algorithm; tree networks; time complexity

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 2
• Strony: 27--37
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Bielak H.

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

autor

Pańczyk M.

• Institute of Computer Science, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 1, 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] Zelinka B., Medians and peripherians of trees, Archivum Mathematicum 4 (2) (1968): 87.
• [6] Bruell S. C., Ghosh S., Karaata M. H., Pemmaraju S. V., Self-stabilizing algorithms for finding centers and medians of trees, SIAM Journal on Computing 29 (1999): 600.
• [7] Blair J. R. S., Manne F., Efficient self-stabilizing algorithms for tree networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, (ICDCS) Providence, Rhode Island (2003): 20.
• [8] Chepoi V., Fevat T., Godard E., Vaxès Y., A self-stabilizing algorithm for the median problem in partial rectangular grids and their relatives, Algorithmica 62 (2012): 146.
• [9] Bielak H., Panczyk M., A self-stabilizing algorithm for median election in some weighted graphs (in preparation).