Distributed Algorithms for Finding Central Paths in Tree Networks
Esther Jennings · The Computer Journal · 1999
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