|
Title |
A Generalized Algorithm for Centrality Problems on Trees |
|
Authors |
Arnon Rosenthal, José A. Pino |
|
Publication date |
April 1989 |
|
Abstract |
A general framework is presented for rapidly analyzing tree networks to compute a measure of the centrality or eccentricity of all vertices in the tree. Several problems, which have been previously described in the literature, fit this framework. Some of these problems have no published solution better than performing a separate traversal for each vertex whose eccentricity is calculated. The method presented in this paper performs just two traversals and yields the eccentricities of all vertices in the tree. Natural sufficient conditions for the algorithm to work in linear time on any given problem are stated. |
|
Downloaded |
1151 times |
|
Pages |
349-361 |
|
Volume |
36 |
|
Journal name |
Journal of the Association for Computing Machinery |
|
Publisher |
ACM Press (New York, NY, USA) |
|
PDF |
|
