An optimal parallel algorithm for computing furthest neighbors in a tree

Abstract

A vertex y is said to be a furthest neighbor of a vertex x in a tree if the weight of the path from x to y is greater than or equal to the weight of the path from x to any other vertex in the tree. We propose a parallel algorithm for computing a furthest neighbor of each vertex in a tree of size n with positive (real-valued) edge weights. The algorithm runs in O(logn) time and O(n) space using O(n/logn) processors on an exclusive-read, exclusive-write parallel RAM. We show that all furthest neighbors of all vertices can also be computed within the same resource bounds. The algorithms are based on an interesting relationship between the diameter of a tree and the furthest neighbor of a vertex.