A self–stabilizing algorithm for finding weighted centroid in trees

Halina Bielak, Michał Pańczyk

Abstract


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:

PDF


DOI: http://dx.doi.org/10.17951/ai.2012.12.2.27-37
Data publikacji: 2012-01-01 00:00:00
Data złożenia artykułu: 2016-04-28 09:07:38

Refbacks

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