Access Restriction

Author Rosenthal, Arnon ♦ Pino, Jos A.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1989
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract A general framework is presented for rapidly analyzing tree networks to compute a measure of the $\textit{centrality}$ or $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1989-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 36
Issue Number 2
Page Count 13
Starting Page 349
Ending Page 361

Open content in new tab

   Open content in new tab
Source: ACM Digital Library