A self–stabilizing algorithm for finding weighted centroid in trees

Halina Bielak, Michał Pańczyk


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.

Full Text:


DOI: http://dx.doi.org/10.2478/v10065-012-0035-x
Data publikacji: 2012-01-01 00:00:00
Data złożenia artykułu: 2016-04-28 09:07:38


Total abstract view - 461
Downloads (from 2020-06-17) - PDF - 0



  • There are currently no refbacks.

Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.