Distributed Algorithms for Finding Centers and Medians in Networks

Abstract

The problem of determining in a distributed fashion the centers and the medians of a network is considered.Lower bounds on the time needed to solve these problems are proved.Algorithms that achieve those bounds for tree networks are presented; the number of exchanged messages is linear in the number of nodes.These techniques are extended to work on general networks in O(n) time units exchanging O(n.e) messages, where n is the number of nodes and e the number of edges in the network.In addition, a comparison with a simple heuristic approach is included.