{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T07:24:47Z","timestamp":1777965887078,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,1]],"date-time":"2017-06-01T00:00:00Z","timestamp":1496275200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["724\/15"],"award-info":[{"award-number":["724\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["523\/12"],"award-info":[{"award-number":["523\/12"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2015813"],"award-info":[{"award-number":["2015813"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00446-017-0304-4","type":"journal-article","created":{"date-parts":[[2017,6,1]],"date-time":"2017-06-01T08:49:19Z","timestamp":1496306959000},"page":"119-137","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On efficient distributed construction of near optimal routing schemes"],"prefix":"10.1007","volume":"31","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,1]]},"reference":[{"issue":"3","key":"304_CR1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0196-6774(90)90017-9","volume":"11","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J. Algorithms 11(3), 307\u2013341 (1990)","journal-title":"J. Algorithms"},{"key":"304_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: Routing with improved communication-space trade-off. In: Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4\u20137, 2004, Proceedings, pp. 305\u2013319 (2004)","DOI":"10.1007\/978-3-540-30186-8_22"},{"key":"304_CR3","doi-asserted-by":"crossref","unstructured":"Bernstein, A.: Fully dynamic (2\u00a0+\u00a0epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25\u201327, 2009, Atlanta, Georgia, USA, pp. 693\u2013702 (2009)","DOI":"10.1109\/FOCS.2009.16"},{"key":"304_CR4","doi-asserted-by":"crossref","unstructured":"Chechik, S.: Compact routing schemes with improved stretch. In: ACM Symposium on Principles of Distributed Computing, PODC \u201913, Montreal, QC, Canada, July 22\u201324, 2013, pp. 33\u201341 (2013)","DOI":"10.1145\/2484239.2484268"},{"issue":"1","key":"304_CR5","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1145\/331605.331610","volume":"47","author":"E Cohen","year":"2000","unstructured":"Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM 47(1), 132\u2013166 (2000)","journal-title":"J. ACM"},{"issue":"1","key":"304_CR6","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"38","author":"L Cowen","year":"2001","unstructured":"Cowen, L.: Compact routing with minimum stretch. J. Algorithms 38(1), 170\u2013183 (2001)","journal-title":"J. Algorithms"},{"issue":"2","key":"304_CR7","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/S0196-6774(03)00002-6","volume":"46","author":"T Eilam","year":"2003","unstructured":"Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms 46(2), 97\u2013114 (2003)","journal-title":"J. Algorithms"},{"issue":"8","key":"304_CR8","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1016\/j.jcss.2006.07.002","volume":"72","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8), 1282\u20131308 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"304_CR9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"M Elkin","year":"2006","unstructured":"Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433\u2013456 (2006)","journal-title":"SIAM J. Comput."},{"key":"304_CR10","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: Hopsets with constant hopbound, and applications to approximate shortest paths. In: 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2016)","DOI":"10.1109\/FOCS.2016.22"},{"key":"304_CR11","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes: Extended abstract. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25\u201328, 2016, pp. 235\u2013244 (2016)","DOI":"10.1145\/2933057.2933098"},{"key":"304_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: Near-optimal scheduling of distributed algorithms. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC \u201915, ACM, New York, NY, USA, pp. 3\u201312 (2015)","DOI":"10.1145\/2767386.2767417"},{"key":"304_CR13","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Distributed Computing\u201427th International Symposium, DISC 2013, Jerusalem, Israel, October 14\u201318, 2013. Proceedings, pp. 1\u201315 (2013)","DOI":"10.1007\/978-3-642-41527-2_1"},{"issue":"1","key":"304_CR14","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1137\/S0097539794261118","volume":"27","author":"JA Garay","year":"1998","unstructured":"Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302\u2013316 (1998)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"304_CR15","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2\u20133), 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"304_CR16","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18\u201321, 2014, pp. 146\u2013155 (2014)","DOI":"10.1109\/FOCS.2014.24"},{"key":"304_CR17","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 489\u2013498 (2016)","DOI":"10.1145\/2897518.2897638"},{"key":"304_CR18","doi-asserted-by":"crossref","unstructured":"Izumi, T., Wattenhofer, R.: Time lower bounds for distributed distance oracles. In: Principles of Distributed Systems\u201418th International Conference, OPODIS 2014, Cortina d\u2019Ampezzo, Italy, December 16\u201319, 2014. Proceedings, pp. 60\u201375 (2014)","DOI":"10.1007\/978-3-319-14472-6_5"},{"issue":"1","key":"304_CR19","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S Kutten","year":"1998","unstructured":"Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40\u201366 (1998)","journal-title":"J. Algorithms"},{"key":"304_CR20","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 381\u2013390 (2013)","DOI":"10.1145\/2488608.2488656"},{"key":"304_CR21","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: ACM Symposium on Principles of Distributed Computing, PODC \u201913, Montreal, QC, Canada, July 22\u201324, 2013, pp. 375\u2013382 (2013)","DOI":"10.1145\/2484239.2484262"},{"key":"304_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebasti\u00e1n, Spain, July 21\u201323, 2015, pp. 153\u2013162 (2015)","DOI":"10.1145\/2767386.2767398"},{"key":"304_CR23","unstructured":"Lenzen, C., Patt-Shamir, B.: Private communication (2016)"},{"key":"304_CR24","unstructured":"Lenzen, C., Patt-Shamir, B., Peleg, D.: Distributed distance computation and routing with small messages (2016) (Unpublished)"},{"key":"304_CR25","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"304_CR26","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/j.tcs.2012.01.006","volume":"444","author":"N Nisse","year":"2012","unstructured":"Nisse, N., Rapaport, I., Suchan, K.: Distributed computing of efficient routing schemes in generalized chordal graphs. Theor. Comput. Sci. 444, 17\u201327 (2012)","journal-title":"Theor. Comput. Sci."},{"key":"304_CR27","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)"},{"issue":"3","key":"304_CR28","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"issue":"5","key":"304_CR29","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"304_CR30","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"issue":"5","key":"304_CR31","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s00446-015-0246-7","volume":"28","author":"AD Sarma","year":"2015","unstructured":"Sarma, A.D., Dinitz, M., Pandurangan, G.: Efficient distributed computation of distance sketches in networks. Distrib. Comput. 28(5), 309\u2013320 (2015)","journal-title":"Distrib. Comput."},{"issue":"5","key":"304_CR32","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1137\/11085178X","volume":"41","author":"AD Sarma","year":"2012","unstructured":"Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235\u20131265 (2012)","journal-title":"SIAM J. Comput."},{"key":"304_CR33","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA \u201901, pp. 1\u201310, New York, NY, USA, ACM (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"304_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0304-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0304-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0304-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T07:11:20Z","timestamp":1569395480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0304-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,1]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["304"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0304-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,1]]}}}