Distributed algorithms for finding central paths in tree networks

Given a graph G = (V, E) and a path P, let d(v, P) be the distance from ver tex v is an element of V to path P. A path-center is a path which minimizes the eccentricity e(P) = max(v is an element of V) d(v, P) such that for ev ery path P' in G, e(P) less than or equal to e(P'), and for every subpath P " subset of P, e(P) < e(P "). Similarly, a core is a path which minimizes the distance d(P) = Sigma(v is an element of V) d(v, P) such that for every path P' in G, d(P) less than or equal to d(P'), and for every subpath P " subset of P, d(P) < d(P "). We present distributed algorithms for finding p ath-centers and cores in asynchronous tree networks, We then extend these t o compute a subset-centrum path in trees which minimizes the distance with respect to a subset of vertices, d(S)(v, P) = Sigma(v is an element of S) d (v, P), where S subset of or equal to V. The time and communication complex ities of these algorithms are O(D) and O (n) respectively, where D is the d iameter and it is the number of vertices (edges) of the network. These algo rithms are asymptotically optimal.