View publication

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 934 times
Pages 349-361
Volume 36
Journal name Journal of the Association for Computing Machinery
Publisher ACM Press (New York, NY, USA)