Distributed algorithms for finding central paths in tree networks

Authors
Citation
E. Jennings, Distributed algorithms for finding central paths in tree networks, COMPUTER J, 42(7), 1999, pp. 609-612
Citations number
12
Categorie Soggetti
Computer Science & Engineering
Journal title
COMPUTER JOURNAL
ISSN journal
00104620 → ACNP
Volume
42
Issue
7
Year of publication
1999
Pages
609 - 612
Database
ISI
SICI code
0010-4620(1999)42:7<609:DAFFCP>2.0.ZU;2-9
Abstract
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.