{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,6]],"date-time":"2023-01-06T10:10:27Z","timestamp":1672999827639},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1989,4]]},"abstract":"\n A general framework is presented for rapidly analyzing tree networks to compute a measure of the\n centrality<\/jats:italic>\n or\n eccentricity<\/jats:italic>\n 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.\n <\/jats:p>","DOI":"10.1145\/62044.62051","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"349-361","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["A generalized algorithm for centrality problems on trees"],"prefix":"10.1145","volume":"36","author":[{"given":"Arnon","family":"Rosenthal","sequence":"first","affiliation":[{"name":"Xerox Advanced Information Technology, Cambridge, MA"}]},{"given":"Jos\u00e9 A.","family":"Pino","sequence":"additional","affiliation":[{"name":"Univ. of Chile, Santiago, Chile"}]}],"member":"320","published-online":{"date-parts":[[1989,4]]},"reference":[{"key":"e_1_2_1_1_2","first-page":"117","volume-title":"Proceedings of the 26th Annual Symposium on Foundations of Computer Science(Portland, Ore., Oct.). IEEE","author":"BERN M. W.","year":"1985","unstructured":"BERN , M. W. , LAWLER , E. L. , AND WONG , A.L. Why certain subgraph computations require only linear time . In Proceedings of the 26th Annual Symposium on Foundations of Computer Science(Portland, Ore., Oct.). IEEE , New York , 1985 , pp. 117 - 125 . BERN, M. W., LAWLER, E. L., AND WONG, A.L. Why certain subgraph computations require only linear time. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science(Portland, Ore., Oct.). IEEE, New York, 1985, pp. 117-125."},{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1002\/net.3230150402","article-title":"Block-vertex duality and the one-median problem","volume":"15","author":"CHEN M. L.","year":"1985","unstructured":"CHEN , M. L. , FRANCIS , R. L. , LAWRENCE , J. F. , LOWE , T. J. , AND TUFEKCI , S . Block-vertex duality and the one-median problem . Networks 15 ( 1985 ), 395 - 412 . CHEN, M. L., FRANCIS, R. L., LAWRENCE, J. F., LOWE, T. J., AND TUFEKCI, S. Block-vertex duality and the one-median problem. Networks 15 (1985), 395-412.","journal-title":"Networks"},{"key":"e_1_2_1_3_2","volume-title":"An Algorithmic Approach","author":"CHRISTOFIDES N.","year":"1975","unstructured":"CHRISTOFIDES , N. Graph Theory , An Algorithmic Approach . Academic Press , Orlando, Fla ., 1975 , Ch. 5-6. CHRISTOFIDES, N. Graph Theory, An Algorithmic Approach. Academic Press, Orlando, Fla., 1975, Ch. 5-6."},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0020-0190(75)90011-3","article-title":"A linear algorithm for the domination number of a tree. inf","volume":"4","author":"COCKAYNE E. J.","year":"1975","unstructured":"COCKAYNE , E. J. , GOODMAN , S. E. , AND HEDETNIEMI , S.T . A linear algorithm for the domination number of a tree. inf . Proc. Lett. 4 ( 1975 ), 41 - 44 . COCKAYNE, E. J., GOODMAN, S. E., AND HEDETNIEMI, S.T. A linear algorithm for the domination number of a tree. inf. Proc. Lett. 4 (1975), 41-44.","journal-title":"Proc. Lett."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/trsc.16.3.265","article-title":"Vertex centers of trees","volume":"16","author":"FARLEY A.M","year":"1982","unstructured":"FARLEY , A.M . Vertex centers of trees . Trans. Sci. 16 , 3 ( Aug. 1982 ), 265-280. FARLEY, A.M. Vertex centers of trees. Trans. Sci. 16, 3 (Aug. 1982), 265-280.","journal-title":"Trans. Sci."},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1287\/trsc.5.2.212","article-title":"Optimal center location in simple networks","volume":"5","author":"GOLDMAN A.J","year":"1971","unstructured":"GOLDMAN , A.J . Optimal center location in simple networks . Trans. Sci. 5 , 2 ( 1971 ), 212-221. GOLDMAN, A.J. Optimal center location in simple networks. Trans. Sci. 5, 2 (1971), 212-221.","journal-title":"Trans. Sci."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1287\/trsc.6.4.407","article-title":"Minimax location of a facility in a network","volume":"6","author":"GOLDMAN A. J","year":"1972","unstructured":"GOLDMAN , A. J . Minimax location of a facility in a network . Trans. Sci. 6 , 4 ( Nov. 1972 ), 407-418. GOLDMAN, A. J. Minimax location of a facility in a network. Trans. Sci. 6, 4 (Nov. 1972), 407-418.","journal-title":"Trans. Sci."},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/opre.12.3.450","article-title":"Optimum locations of switching centers and the absolute centers and medians of a graph","volume":"12","author":"HAKIMI S.L","year":"1964","unstructured":"HAKIMI , S.L . Optimum locations of switching centers and the absolute centers and medians of a graph . Op. Res. 12 , 3 ( May-June 1964 ), 450-459. HAKIMI, S.L. Optimum locations of switching centers and the absolute centers and medians of a graph. Op. Res. 12, 3 (May-June 1964), 450-459.","journal-title":"Op. Res."},{"key":"e_1_2_1_9_2","volume-title":"On p-centers in Networks. Trans. Sci. 12, l (Feb","author":"HAKIMI S. L.","year":"1978","unstructured":"HAKIMI , S. L. , SCHMEICHEL , E. F. , AND PIERCE , J.G. On p-centers in Networks. Trans. Sci. 12, l (Feb . 1978 ), 1-15. HAKIMI, S. L., SCHMEICHEL, E. F., AND PIERCE, J.G. On p-centers in Networks. Trans. Sci. 12, l (Feb. 1978), 1-15."},{"key":"e_1_2_1_10_2","volume-title":"On finding the absolute and vertex centers of a tree with distances. Trans. Sci. 8, l (Feb","author":"HALFIN S.","year":"1974","unstructured":"HALFIN , S. On finding the absolute and vertex centers of a tree with distances. Trans. Sci. 8, l (Feb . 1974 ), 75-77. HALFIN, S. On finding the absolute and vertex centers of a tree with distances. Trans. Sci. 8, l (Feb. 1974), 75-77."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1287\/trsc.7.3.287","article-title":"Minimax location of a facility in an undirected tree graph","volume":"7","author":"HANDLER G.Y","year":"1973","unstructured":"HANDLER , G.Y . Minimax location of a facility in an undirected tree graph . Trans. Sci. 7 , 3 ( Aug. 1973 ), 287-293. HANDLER, G.Y. Minimax location of a facility in an undirected tree graph. Trans. Sci. 7, 3 (Aug. 1973), 287-293.","journal-title":"Trans. Sci."},{"key":"e_1_2_1_12_2","first-page":"113","article-title":"Single facility location on networks","volume":"31","author":"HANSEN P.","year":"1987","unstructured":"HANSEN , P. , LABBE , M. , PELTERS , D. , AND THISSE , J.F . Single facility location on networks . Ann. Discrete Math. 31 ( 1987 ), 113 - 145 . HANSEN, P., LABBE, M., PELTERS, D., AND THISSE, J.F. Single facility location on networks. Ann. Discrete Math. 31 (1987), 113-145.","journal-title":"Ann. Discrete Math."},{"key":"e_1_2_1_13_2","first-page":"2","author":"HARARY F.","year":"1969","unstructured":"HARARY , F. Graph Theory. Addison-Wesley, Reading , Mass. , 1969 , C h. 2 - 4 . HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969, Ch. 2-4.","journal-title":"Mass."},{"key":"e_1_2_1_14_2","unstructured":"HEDETNIEMi S. M. COCKAYNE E. J. AND HEDETNIEMI S.T. Linear algorithms for finding the Ir~rA~n o.nlpr ~nA n~th p~nt~r hf~ ~ Ir~o Yrnnc ~ri I i 9 IM~x~ I OR I) QR_ I 1 4 HEDETNIEMi S. M. COCKAYNE E. J. AND HEDETNIEMI S.T. Linear algorithms for finding the Ir~rA~n o.nlpr ~nA n~th p~nt~r hf~ ~ Ir~o Yrnnc ~ri I i 9 IM~x~ I OR I) QR_ I 1 4"},{"key":"e_1_2_1_15_2","volume-title":"Application of mathematical methods to wheat harvesting. Math. Sin. II, l","author":"HUA L. K.","year":"1961","unstructured":"HUA , L. K. , ET AL . Application of mathematical methods to wheat harvesting. Math. Sin. II, l ( 1961 ), 77-91. HUA, L. K., ET AL. Application of mathematical methods to wheat harvesting. Math. Sin. II, l (1961), 77-91."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0020-0190(75)90055-1","article-title":"Some properties of a centroid of a free tree","volume":"4","author":"KANG A.","year":"1975","unstructured":"KANG , A. , AND AULT , D . Some properties of a centroid of a free tree . Inf. Proc. Lett. 4 ( 1975 ), 18 - 20 . KANG, A., AND AULT, D. Some properties of a centroid of a free tree. Inf. Proc. Lett. 4 (1975), 18-20.","journal-title":"Inf. Proc. Lett."},{"key":"e_1_2_1_17_2","first-page":"3","article-title":"An algorithmic approach to network location problems, I: The p-centers","volume":"37","author":"KARIV O.","year":"1979","unstructured":"KARIV , O. , AND HAKIMI , S. L . An algorithmic approach to network location problems, I: The p-centers . SIAM J. Appl. Math. 37 , 3 ( 1979 ), 513-538. KARIV, O., AND HAKIMI, S. L. An algorithmic approach to network location problems, I: The p-centers. SIAM J. Appl. Math. 37, 3 (1979), 513-538.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_2_1_18_2","first-page":"3","article-title":"An algorithmic approach to network location problems, II: The p-medians","volume":"37","author":"KARIV O.","year":"1979","unstructured":"KARIV , O. , AND HAKIMI , S.L . An algorithmic approach to network location problems, II: The p-medians . SIAM J. Appl. Math. 37 , 3 ( 1979 ), 539-560. KARIV, O., AND HAKIMI, S.L. An algorithmic approach to network location problems, II: The p-medians. SIAM J. Appl. Math. 37, 3 (1979), 539-560.","journal-title":"SIAM J. Appl. Math."},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1002\/net.3230030107","article-title":"Recursive analysis of network reliability","volume":"3","author":"KERSHENBAUM A.","year":"1973","unstructured":"KERSHENBAUM , A. , AND VAN SLYKE , R . Recursive analysis of network reliability . Networks 3 ( 1973 ), 81 - 94 . KERSHENBAUM, A., AND VAN SLYKE, R. Recursive analysis of network reliability. Networks 3 (1973), 81-94.","journal-title":"Networks"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1137\/0212052","article-title":"Linear-time algorithms for linear programming in R3 and related problems","volume":"12","author":"MEGIDDO N","year":"1983","unstructured":"MEGIDDO , N . Linear-time algorithms for linear programming in R3 and related problems . SIAM J. Comput. 12 , 4 ( Nov. 1983 ), 759-776. MEGIDDO, N. Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput. 12, 4 (Nov. 1983), 759-776.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_21_2","volume-title":"Optimal source location to feed a iossy distribution tree. IISI:,L lrans. Circ. l-'heory 20, 3 (May","author":"SHVK~L J.","year":"1973","unstructured":"SHVK~L , J. Optimal source location to feed a iossy distribution tree. IISI:,L lrans. Circ. l-'heory 20, 3 (May 1973 ), 246-250. SHVK~L, J. Optimal source location to feed a iossy distribution tree. IISI:,L lrans. Circ. l-'heory 20, 3 (May 1973), 246-250."},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321964"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/322326.322328"},{"key":"e_1_2_1_24_2","unstructured":"TANSEL B. C. FRANCIS R. L. AND LOWE T.J. Location on networks: A survey. Part I: The TANSEL B. C. FRANCIS R. L. AND LOWE T.J. Location on networks: A survey. Part I: The"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/62044.62051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T20:39:27Z","timestamp":1672691967000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/62044.62051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,4]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1989,4]]}},"alternative-id":["10.1145\/62044.62051"],"URL":"http:\/\/dx.doi.org\/10.1145\/62044.62051","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1989,4]]},"assertion":[{"value":"1989-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}