{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T06:46:57Z","timestamp":1769928417319,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315848","type":"print"},{"value":"9783642315855","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31585-5_58","type":"book-chapter","created":{"date-parts":[[2012,6,23]],"date-time":"2012-06-23T07:56:29Z","timestamp":1340438189000},"page":"660-672","source":"Crossref","is-referenced-by-count":52,"title":["Distributed Algorithms for Network Diameter and Girth"],"prefix":"10.1007","author":[{"given":"David","family":"Peleg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liam","family":"Roditty","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Tal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"58_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D. Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput.\u00a028(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Almeida, P.S., Baquero, C., Cunha, A.: Fast distributed computation of distances in networks. Technical report (2011)","DOI":"10.1109\/CDC.2012.6426872"},{"key":"58_CR3","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1109\/12.144623","volume":"41","author":"J.K. Antonio","year":"1992","unstructured":"Antonio, J.K., Huang, G.M., Tsai, W.K.: A fast distributed shortest path algorithm for a class of hierarchically clustered data networks. IEEE Trans. Computers\u00a041, 710\u2013724 (1992)","journal-title":"IEEE Trans. Computers"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: FOCS, pp. 591\u2013602. IEEE Computer Society (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"58_CR5","doi-asserted-by":"crossref","first-page":"16","DOI":"10.4304\/jcp.2.9.16-26","volume":"2","author":"S. Cicerone","year":"2007","unstructured":"Cicerone, S., D\u2019Angelo, G., Di Stefano, G., Frigioni, D., Petricola, A.: Partially dynamic algorithms for distributed shortest paths and their experimental evaluation. J. Computers\u00a02, 16\u201326 (2007)","journal-title":"J. Computers"},{"issue":"1","key":"58_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1109\/TSE.1987.232560","volume":"13","author":"I. Cidon","year":"1987","unstructured":"Cidon, I., Jaffe, J.M., Sidi, M.: Local distributed deadlock detection by cycle detection and clustering. IEEE Trans. Software Eng.\u00a013(1), 3\u201314 (1987)","journal-title":"IEEE Trans. Software Eng."},{"key":"58_CR7","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W.: A note on two problems in connection with graphs. Numer. Math., 269\u2013271 (1959)","DOI":"10.1007\/BF01386390"},{"issue":"5","key":"58_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput.\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"58_CR9","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin, M.: Computing almost shortest paths. ACM Transactions on Algorithms\u00a01(2), 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms"},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: shortest path. Comm. ACM\u00a05, 345 (1962)","journal-title":"Comm. ACM"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Proc. 23rd ACM-SIAM Symp. on Discrete Algorithms, SODA (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Haldar, S.: An \u2019all pairs shortest paths\u2019 distributed algorithm using 2n\n                  2 messages. J. Algorithms, 20\u201336 (1997)","DOI":"10.1006\/jagm.1996.0842"},{"key":"58_CR13","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Proc. 31st Annual ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, PODC (2012)","DOI":"10.1145\/2332432.2332504"},{"issue":"4","key":"58_CR14","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Computing\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM J. Computing"},{"key":"58_CR15","unstructured":"Kanchi, S., Vineyard, D.: Time optimal distributed all pairs shortest path problem. Int. J. of Information Theories and Applications, 141\u2013146 (2004)"},{"issue":"4","key":"58_CR16","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/j.cosrev.2009.08.001","volume":"3","author":"T. Kavitha","year":"2009","unstructured":"Kavitha, T., Liebchen, C., Mehlhorn, K., Michail, D., Rizzi, R., Ueckerdt, T., Zweig, K.A.: Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review\u00a03(4), 199\u2013243 (2009)","journal-title":"Computer Science Review"},{"key":"58_CR17","unstructured":"Krivelevich, M., Nutov, Z., Yuster, R.: Approximation algorithms for cycle packing problems. In: Proc. SODA, pp. 556\u2013561 (2005)"},{"issue":"10","key":"58_CR18","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1016\/j.ipl.2009.01.008","volume":"109","author":"A. Lingas","year":"2009","unstructured":"Lingas, A., Lundell, E.-M.: Efficient approximation algorithms for shortest cycles in undirected graphs. Inf. Process. Lett.\u00a0109(10), 493\u2013498 (2009)","journal-title":"Inf. Process. Lett."},{"key":"58_CR19","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"58_CR20","doi-asserted-by":"crossref","unstructured":"Roditty, L., Tov, R.: Approximating the girth. In: Proc. SODA, pp. 1446\u20131454 (2011)","DOI":"10.1137\/1.9781611973082.112"},{"key":"58_CR21","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Minimum weight cycles and triangles: Equivalences and algorithms. In: Proc. FOCS, pp. 180\u2013189 (2011)","DOI":"10.1109\/FOCS.2011.27"},{"key":"58_CR22","doi-asserted-by":"crossref","unstructured":"Roditty, L., Vassilevska Williams, V.: Subquadratic time approximation algorithms for the girth. In: SODA, pp. 833\u2013845 (2012)","DOI":"10.1137\/1.9781611973099.67"},{"key":"58_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TIT.1983.1056620","volume":"IT-29","author":"A. Segall","year":"1983","unstructured":"Segall, A.: Distributed network protocols. IEEE Trans. Inf. Th.\u00a0IT-29, 23\u201335 (1983)","journal-title":"IEEE Trans. Inf. Th."},{"key":"58_CR24","first-page":"400","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. JCSS\u00a051, 400\u2013403 (1995)","journal-title":"JCSS"},{"issue":"1","key":"58_CR25","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S. Warshall","year":"1962","unstructured":"Warshall, S.: A theorem on boolean matrices. J. ACM\u00a09(1), 11\u201312 (1962)","journal-title":"J. ACM"},{"key":"58_CR26","unstructured":"Vassilevska Williams, V.: Private communication"},{"key":"58_CR27","unstructured":"Vassilevska Williams, V.: Breaking the coppersmith-winograd barrier. In: STOC (2012)"},{"key":"58_CR28","unstructured":"Yuster, R.: Computing the diameter polynomially faster than apsp. CoRR, abs\/1011.6181 (2010)"},{"issue":"3","key":"58_CR29","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All pairs shortest paths using bridging sets and rectangular matrix multiplication. JACM\u00a049(3), 289\u2013317 (2002)","journal-title":"JACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31585-5_58.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T08:13:50Z","timestamp":1620116030000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31585-5_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315848","9783642315855"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31585-5_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}