A simple parallel algorithm for computing the diameters of all vertices in a tree and its application

The problem considered here is to find, for all vertices v in a given tree T , the maximum among the distances from v to all other vertices in T . We show that this problem can be solved in O(log n ) time using O( n /log n ) processors on an EREW PRAM, where n is the number of vertices in the tree. The correctness of the algorithm relies on two simple but interesting properties of trees. We then show an application of the result.