{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:46:56Z","timestamp":1725558416456},"publisher-location":"Berlin, Heidelberg","reference-count":40,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642137303"},{"type":"electronic","value":"9783642137310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_6","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T07:00:50Z","timestamp":1276153250000},"page":"50-61","source":"Crossref","is-referenced-by-count":0,"title":["The Emergence of Sparse Spanners and Greedy Well-Separated Pair Decomposition"],"prefix":"10.1007","author":[{"given":"Jie","family":"Gao","sequence":"first","affiliation":[]},{"given":"Dengpan","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"6_CR1","unstructured":"http:\/\/www.aqualab.cs.northwestern.edu\/projects\/Ono.html"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Goldberg, A.V., Malkhi, D.: Routing in networks with low doubling dimension. In: Proc. of the 26th International Conference on Distributed Computing Systems (ICDCS) (July 2006)","DOI":"10.1109\/ICDCS.2006.72"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1145\/1011767.1011789","volume-title":"PODC \u201904: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing","author":"I. Abraham","year":"2004","unstructured":"Abraham, I., Malkhi, D.: Compact routing on euclidian metrics. In: PODC \u201904: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pp. 141\u2013149. ACM, New York (2004)"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1109557.1109568","volume-title":"SODA \u201906: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm","author":"S. Albers","year":"2006","unstructured":"Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On nash equilibria for a network creation game. In: SODA \u201906: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 89\u201398. ACM, New York (2006)"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.: Euclidean spanners: short, thin, and lanky. In: Proc. 27th ACM Symposium on Theory Computing, pp. 489\u2013498 (1995)","DOI":"10.1145\/225058.225191"},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"Arya, S., Mount, D.M., Smid, M.: Randomized and deterministic algorithms for geometric spanners of small diameter. In: Proc. 35th IEEE Symposium on Foundations of Computer Science, pp. 703\u2013712 (1994)","DOI":"10.1109\/SFCS.1994.365722"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02523237","volume":"17","author":"S. Arya","year":"1997","unstructured":"Arya, S., Smid, M.: Efficient construction of a bounded-degree spanner with low weight. Algorithmica\u00a017, 33\u201354 (1997)","journal-title":"Algorithmica"},{"key":"6_CR8","first-page":"46","volume-title":"9th Workshop on Algorithm Enginneering and Experiments (ALENEX\u201907)","author":"H. Bast","year":"2007","unstructured":"Bast, H., Funke, S., Matijevic, D., Sanders, P., Schultes, D.: In transit to constant time shortest-path queries in road networks. In: Applegate, D., Brodal, G. (eds.) 9th Workshop on Algorithm Enginneering and Experiments (ALENEX\u201907), New Orleans, USA, pp. 46\u201359. SIAM, Philadelphia (2007)"},{"key":"6_CR9","unstructured":"Callahan, Kosaraju: Faster algorithms for some geometric graph problems in higher dimensions. In: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms, pp. 291\u2013300 (1993)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Callahan, P.B.: Optimal parallel all-nearest-neighbors using the well-separated pair decomposition. In: Proc. 34th IEEE Symposium on Foundations of Computer Science, pp. 332\u2013340 (1993)","DOI":"10.1109\/SFCS.1993.366854"},{"key":"6_CR11","unstructured":"Callahan, P.B., Kosaraju, S.R.: Algorithms for dynamic closest-pair and n-body potential fields. In: Proc. 6th ACM-SIAM Symposium on Discrete Algorithms, pp. 263\u2013272 (1995)"},{"key":"6_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P.B. Callahan","year":"1995","unstructured":"Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM\u00a042, 67\u201390 (1995)","journal-title":"J. ACM"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1142\/S0218195995000088","volume":"5","author":"B. Chandra","year":"1995","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. Internat. J. Comput. Geom. Appl.\u00a05, 125\u2013144 (1995)","journal-title":"Internat. J. Comput. Geom. Appl."},{"issue":"4","key":"6_CR14","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1145\/964723.383064","volume":"31","author":"Y. Chu","year":"2001","unstructured":"Chu, Y., Rao, S., Seshan, S., Zhang, H.: Enabling conferencing applications on the internet using an overlay muilticast architecture. SIGCOMM Comput. Commun. Rev.\u00a031(4), 55\u201367 (2001)","journal-title":"SIGCOMM Comput. Commun. Rev."},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1145\/1073814.1073833","volume-title":"PODC \u201905: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing","author":"J. Corbo","year":"2005","unstructured":"Corbo, J., Parkes, D.: The price of selfish behavior in bilateral network formation. In: PODC \u201905: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pp. 99\u2013107. ACM, New York (2005)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: Proc. 9th Annu. ACM Sympos. Comput. Geom., pp. 53\u201362 (1993)","DOI":"10.1145\/160985.160998"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1142\/S0218195997000193","volume":"7","author":"G. Das","year":"1997","unstructured":"Das, G., Narasimhan, G.: A fast algorithm for constructing sparse Euclidean spanners. Internat. J. Comput. Geom. Appl.\u00a07, 297\u2013315 (1997)","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"6_CR18","unstructured":"Das, G., Narasimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proc. 6th ACM-SIAM Sympos. Discrete Algorithms, pp. 215\u2013222 (1995)"},{"key":"6_CR19","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/B978-044482537-7\/50010-3","volume-title":"Handbook of Computational Geometry","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 425\u2013461. Elsevier Science Publishers B.V., North-Holland (2000)"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Erickson, J.: Dense point sets have sparse Delaunay triangulations. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 125\u2013134 (2002)","DOI":"10.1145\/378583.378636"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: PODC \u201903: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 347\u2013351 (2003)","DOI":"10.1145\/872035.872088"},{"issue":"1-2","key":"6_CR22","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/j.comgeo.2005.10.001","volume":"35","author":"J. Gao","year":"2006","unstructured":"Gao, J., Guibas, L., Nguyen, A.: Deformable spanners and their applications. Computational Geometry: Theory and Applications\u00a035(1-2), 2\u201319 (2006)","journal-title":"Computational Geometry: Theory and Applications"},{"key":"6_CR23","unstructured":"Gottlieb, L.-A., Roditty, L.: Improved algorithms for fully dynamic geometric spanners and geometric routing. In: SODA \u201908: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 591\u2013600. Society for Industrial and Applied Mathematics (2008)"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Levcopoulos, C., Narasimhan, G., Smid, M.: Approximate distance oracles for geometric graphs. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 828\u2013837 (2002)","DOI":"10.1007\/3-540-36136-7_32"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: FOCS \u201903: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"6_CR26","doi-asserted-by":"publisher","first-page":"931","DOI":"10.1145\/1276958.1277147","volume-title":"GECCO \u201907: Proceedings of the 9th annual conference on Genetic and evolutionary computation","author":"T. Jansen","year":"2007","unstructured":"Jansen, T., Theile, M.: Stability in the self-organized evolution of networks. In: GECCO \u201907: Proceedings of the 9th annual conference on Genetic and evolutionary computation, pp. 931\u2013938. ACM, New York (2007)"},{"key":"6_CR27","doi-asserted-by":"crossref","unstructured":"Konjevod, G., Richa, A.W., Xia, D.: Optimal-stretch name-independent compact routing in doubling metrics. In: PODC \u201906: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 198\u2013207 (2006)","DOI":"10.1145\/1146381.1146412"},{"key":"6_CR28","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/507670.507688","volume-title":"NOSSDAV \u201902: Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video","author":"M. Kwon","year":"2002","unstructured":"Kwon, M., Fahmy, S.: Topology-aware overlay networks for group communication. In: NOSSDAV \u201902: Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, pp. 127\u2013136. ACM, New York (2002)"},{"issue":"1","key":"6_CR29","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00453-001-0075-x","volume":"32","author":"C. Levcopoulos","year":"2002","unstructured":"Levcopoulos, C., Narasimhan, G., Smid, M.H.M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica\u00a032(1), 144\u2013156 (2002)","journal-title":"Algorithmica"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Lua, K., Crowcroft, J., Pias, M., Sharma, R., Lim, S.: A survey and comparison of peer-to-peer overlay network schemes. IEEE Communications Surveys & Tutorials, 72\u201393 (2005)","DOI":"10.1109\/COMST.2005.1610546"},{"key":"6_CR31","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1145\/1146381.1146403","volume-title":"PODC \u201906: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing","author":"T. Moscibroda","year":"2006","unstructured":"Moscibroda, T., Schmid, S., Wattenhofer, R.: On the topologies formed by selfish peers. In: PODC \u201906: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 133\u2013142. ACM, New York (2006)"},{"key":"6_CR32","doi-asserted-by":"publisher","first-page":"978","DOI":"10.1137\/S0097539799361671","volume":"30","author":"G. Narasimhan","year":"2000","unstructured":"Narasimhan, G., Smid, M.: Approximating the stretch factor of Euclidean graphs. SIAM J. Comput.\u00a030, 978\u2013989 (2000)","journal-title":"SIAM J. Comput."},{"key":"6_CR33","doi-asserted-by":"publisher","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 (2007)"},{"key":"6_CR34","volume-title":"Monographs on Discrete Mathematics and Applications","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality Sensitive Approach. In: Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (2000)"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Ratnasamy, S., Handley, M., Karp, R., Shenker, S.: Topologically-aware overlay construction and server selection. In: Proceedings of the 21th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905), vol.\u00a03, pp. 1190\u20131199 (2002)","DOI":"10.1109\/INFCOM.2002.1019369"},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1007\/11841036_71","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Sanders","year":"2006","unstructured":"Sanders, P., Schultes, D.: Engineering highway hierarchies. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 804\u2013816. Springer, Heidelberg (2006)"},{"key":"6_CR37","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: PODC \u201905: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"6_CR38","volume-title":"Computer networks (3rd ed.)","author":"A.S. Tanenbaum","year":"1996","unstructured":"Tanenbaum, A.S.: Computer networks (3rd ed.). Prentice-Hall, Inc., Upper Saddle River (1996)"},{"key":"6_CR39","doi-asserted-by":"crossref","unstructured":"Wang, W., Jin, C., Jamin, S.: Network overlay construction under limited end-to-end reachability. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM\u201905), March 2005, vol.\u00a03, pp. 2124\u20132134 (2005)","DOI":"10.1109\/INFCOM.2005.1498488"},{"key":"6_CR40","first-page":"1","volume-title":"MG \u201908: Proceedings of the 15th ACM Mardi Gras conference","author":"X. Zhang","year":"2008","unstructured":"Zhang, X., Li, Z., Wang, Y.: A distributed topology-aware overlays construction algorithm. In: MG \u201908: Proceedings of the 15th ACM Mardi Gras conference, pp. 1\u20136. ACM, New York (2008)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,1]],"date-time":"2023-06-01T10:37:10Z","timestamp":1685615830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":40,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}