{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T10:37:29Z","timestamp":1773830249576,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1007\/s00446-009-0091-7","type":"journal-article","created":{"date-parts":[[2009,11,30]],"date-time":"2009-11-30T15:09:36Z","timestamp":1259593776000},"page":"147-166","source":"Crossref","is-referenced-by-count":26,"title":["Distributed algorithms for ultrasparse spanners and linear size skeletons"],"prefix":"10.1007","volume":"22","author":[{"given":"Seth","family":"Pettie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,12,1]]},"reference":[{"key":"91_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: On space-stretch trade-offs: upper bounds. In: Proceedings of the 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 217\u2013224 (2006)","DOI":"10.1145\/1148109.1148144"},{"key":"91_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. In: Proceedings of the 16th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) pp. 20\u201324 (2004)","DOI":"10.1145\/1007912.1007916"},{"issue":"4","key":"91_CR3","doi-asserted-by":"crossref","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. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"91_CR4","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer I., Das G., Dobkin D., Joseph D., Soares J.: On sparse spanners of weighted graphs. Discrete Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"91_CR5","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.ipl.2007.11.001","volume":"106","author":"S. Baswana","year":"2008","unstructured":"Baswana S.: Streaming algorithm for graph spanners\u2014single pass and constant processing time per edge. Inf. Proc. Lett. 106(3), 110\u2013114 (2008)","journal-title":"Inf. Proc. Lett."},{"key":"91_CR6","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 591\u2013602. (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"91_CR7","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (\u03b1, \u03b2)-spanners. ACM Trans. on Algorithms (2009)","DOI":"10.1145\/1868237.1868242"},{"key":"91_CR8","unstructured":"Baswana, S., Sarkar, S.: Fully dynamic algorithms for graph spanners with poly-logaritmic update time. In: Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1125\u20131134 (2008)"},{"issue":"4","key":"91_CR9","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S. Baswana","year":"2006","unstructured":"Baswana S., Sen S.: Approximate distance oracles for unweighted graphs in expected O(n 2 log n) time. ACM Trans. Algorithms 2(4), 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"91_CR10","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S. Baswana","year":"2007","unstructured":"Baswana S., Sen S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. J. Random Struct. Algs. 30(4), 532\u2013563 (2007)","journal-title":"J. Random Struct. Algs."},{"key":"91_CR11","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1006\/jagm.2000.1134","volume":"28","author":"L.J. Cowen","year":"2001","unstructured":"Cowen L.J.: Compact routing with minimum stretch. J. Algor. 28, 170\u2013183 (2001)","journal-title":"J. Algor."},{"issue":"1","key":"91_CR12","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.jalgor.2003.08.001","volume":"50","author":"L.J. Cowen","year":"2004","unstructured":"Cowen L.J., Wagner C.G.: Compact roundtrip routing in directed networks. J. Algor. 50(1), 79\u201395 (2004)","journal-title":"J. Algor."},{"issue":"1\u20132","key":"91_CR13","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1016\/j.tcs.2008.02.019","volume":"399","author":"B. Derbel","year":"2008","unstructured":"Derbel B., Gavoille C.: Fast deterministic distributed algorithms for sparse spanners. Theor. Comput. Sci. 399(1\u20132), 83\u2013100 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"91_CR14","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg D.: Deterministic distributed construction of linear stretch spanners in polylogarithmic time. In: Proceedings of the 21st International Symposium on Distributed Computing (DISC) pp. 179\u2013192. (2007)","DOI":"10.1007\/978-3-540-75142-7_16"},{"key":"91_CR15","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: Proceedings 27th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 273\u2013282. (2008)","DOI":"10.1145\/1400751.1400788"},{"key":"91_CR16","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: Local computation of nearly additive spanners. In: Proceedings 23rd International Symposium on Distributed Computing (DISC), LNCS volume 5805, pp. 176\u2013190. (2009)","DOI":"10.1007\/978-3-642-04355-0_20"},{"issue":"5","key":"91_CR17","doi-asserted-by":"crossref","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. 29(5), 1740\u20131759 (2000)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"91_CR18","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1016\/j.jcss.2005.04.002","volume":"71","author":"D. Dubhashi","year":"2005","unstructured":"Dubhashi D., Mei A., Panconesi A., Radhakrishnan J., Srinivasan A.: Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. J. Comput. Syst. Sci. 71(4), 467\u2013479 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"91_CR19","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/1103963.1103968","volume":"1","author":"M. Elkin","year":"2005","unstructured":"Elkin M.: Computing almost shortest paths. ACM Trans. Algorithms 1(2), 283\u2013323 (2005)","journal-title":"ACM Trans. Algorithms"},{"key":"91_CR20","doi-asserted-by":"crossref","unstructured":"Elkin, M.: A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In: Proceedings of the 26th International Symposium on Principles of Distributed Computing (PODC), pp. 185\u2013194 (2007)","DOI":"10.1145\/1281100.1281128"},{"key":"91_CR21","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for maintaining sparse spanners. In: Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 716\u2013727 (2007)","DOI":"10.1007\/978-3-540-73420-8_62"},{"key":"91_CR22","doi-asserted-by":"crossref","unstructured":"Elkin, M., Peleg, D.: $${(1+\\epsilon, \\beta)}$$ -spanner constructions for general graphs. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 173\u2013182 (2001)","DOI":"10.1145\/380752.380797"},{"issue":"3","key":"91_CR23","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin M., Peleg D.: $${(1+\\epsilon, \\beta)}$$ -spanner constructions for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"91_CR24","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/s00446-005-0147-2","volume":"18","author":"M. Elkin","year":"2006","unstructured":"Elkin M., Zhang J.: Efficient algorithms for constructing $${(1+\\epsilon, \\beta)}$$ -spanners in the distributed and streaming models. Distrib. Comput. 18(5), 375\u2013385 (2006)","journal-title":"Distrib. Comput."},{"key":"91_CR25","unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In Theory of Graphs and its Applications (Proceedings of Symposium Smolenice, 1963), pp. 29\u201336. Publ. House Czechoslovak Acad. Sci., Prague (1963)"},{"key":"91_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C. Gavoille","year":"2004","unstructured":"Gavoille C., Peleg D., P\u00e9rennes S., Raz R.: Distance labeling in graphs. J. Algor. 53, 85\u2013112 (2004)","journal-title":"J. Algor."},{"issue":"2","key":"91_CR27","doi-asserted-by":"crossref","first-page":"253","DOI":"10.4171\/JEMS\/79","volume":"9","author":"M. Mendel","year":"2007","unstructured":"Mendel M., Naor A.: Ramsey partitions and proximity data structures. J. Eur. Math. Soc 9(2), 253\u2013275 (2007)","journal-title":"J. Eur. Math. Soc"},{"key":"91_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546884","volume-title":"Geometric Spanner Networks","author":"G. Narasimhan","year":"2007","unstructured":"Narasimhan G., Smid M.: Geometric Spanner Networks. Cambridge University Press, Cambridge, England (2007)"},{"key":"91_CR29","unstructured":"Panconesi, A.: Personal communication (2008)"},{"key":"91_CR30","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"3","key":"91_CR31","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 amd efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"91_CR32","unstructured":"Pettie, S.: Low distortion spanners. ACM Trans. on Algorithms (to appear)"},{"key":"91_CR33","doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low distortion spanners. In: Proceedings of the 34th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 78\u201389 (2007)","DOI":"10.1007\/978-3-540-73420-8_9"},{"key":"91_CR34","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. In: Proceedings of the 13th ACM-SIAM Symposium On Discrete Algorithms (SODA), pp. 844\u2013851 (2002)"},{"key":"91_CR35","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"91_CR36","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Proceedings of the 12th Annual European Symposium on Algorithms (ESA), pp. 580\u2013591 (2004)","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"91_CR37","doi-asserted-by":"crossref","unstructured":"Thorup, M. Zwick, U.: Compact routing schemes. In: Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"91_CR38","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"},{"key":"91_CR39","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"issue":"1","key":"91_CR40","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0095-8956(91)90097-4","volume":"52","author":"R. Wenger","year":"1991","unstructured":"Wenger R.: Extremal graphs with no C 4s, C 6s, or C 10s. J. Comb. Theory Ser. B 52(1), 113\u2013116 (1991)","journal-title":"J. Comb. Theory Ser. B"},{"key":"91_CR41","doi-asserted-by":"crossref","unstructured":"Woodruff, D.: Lower bounds for additive spanners, emulators, and more. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 389\u2013398 (2006)","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-009-0091-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-009-0091-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-009-0091-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:26:43Z","timestamp":1559136403000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-009-0091-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12,1]]},"references-count":41,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["91"],"URL":"https:\/\/doi.org\/10.1007\/s00446-009-0091-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12,1]]}}}