© 1999 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
Distributed Algorithms for Finding Central Paths in Tree Networks
A1 Computer Science Department, California State Polytechnic University, Pomona Email: ehjennings@csupomona.edu
Given a graph $G=(V,E)$ and a path $P$, let $d(v,P)$ be the distance from vertex $v \in V$ to path $P$. A path-center is a path which minimizes the eccentricity $e(P) = {\rm max}_{v\in V}\, d(v,P)$ such that for every path $P'$ in $G$, $e(P) \leq e(P')$, and for every subpath $P'' \subset P$, $e(P)s<se(P'')$. Similarly, a core is a path which minimizes the distance $d(P) = \sum_{v \in V}\, d(v,P)$ such that for every path $P'$ in $G$, $d(P) \leq d(P')$, and for every subpath $P'' \subset P$, $d(P)s<sd(P'')$. We present distributed algorithms for finding path-centers and cores in asynchronous tree networks. We then extend these to compute a subset-centrum path in trees which minimizes the distance with respect to a subset of vertices, $d_S(v,P) = \sum_{v \in S} d(v,P)$, where $S \subseteq V$. The time and communication complexities of these algorithms are $O(D)$ and $O(n)$ respectively, where $D$ is the diameter and $n$ is the number of vertices (edges) of the network. These algorithms are asymptotically optimal.
Received 17 April, 1997. Revised 30 August, 1999.