{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:28:15Z","timestamp":1766136495648,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_37","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"442-452","source":"Crossref","is-referenced-by-count":5,"title":["Light Spanners"],"prefix":"10.1007","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Cost-sensitive analysis of communication protocols. In: Proc. of 9th PODC, pp. 177\u2013187 (1990)","key":"37_CR1","DOI":"10.21236\/ADA237356"},{"unstructured":"Awerbuch, B., Baratz, A., Peleg, D.: Efficient broadcast and light-weight spanners (1991) (manuscript)","key":"37_CR2"},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Alth\u00f6fer","year":"1993","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D.P., Joseph, D., Soares, J.: On sparse spanners of weighted graphs. Discrete & Computational Geometry\u00a09, 81\u2013100 (1993)","journal-title":"Discrete & Computational Geometry"},{"doi-asserted-by":"crossref","unstructured":"Arya, S., Das, G., Mount, D.M., Salowe, J.S., Smid, M.H.M.: Euclidean spanners: short, thin, and lanky. In: Proc. of 27th STOC, pp. 489\u2013498 (1995)","key":"37_CR4","DOI":"10.1145\/225058.225191"},{"unstructured":"Braynard, R., Kostic, D., Rodriguez, A., Chase, J., Vahdat, A.: Opus: an overlay peer utility service. In: Prof. of 5th OPENARCH (2002)","key":"37_CR5"},{"doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic press, London (1978)","key":"37_CR6","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"37_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/3-540-45061-0_32","volume-title":"Automata, Languages and Programming","author":"S. Baswana","year":"2003","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing a (2k\u2009\u2212\u20091)-spanner of O(n 1\u2009+\u20091\/k ) size in weighted graphs. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 384\u2013396. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","unstructured":"Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. In: Proc. of 8th SOCG, pp. 192\u2013201 (1992)","key":"37_CR8","DOI":"10.1145\/142675.142717"},{"key":"37_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-39206-1_27","volume-title":"Automata, Languages, and Programming","author":"T.-H.H. Chan","year":"2013","unstructured":"Chan, T.-H.H., Li, M., Ning, L., Solomon, S.: New doubling spanners: Better and simpler. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 315\u2013327. Springer, Heidelberg (2013)"},{"doi-asserted-by":"crossref","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. In: Proc. of 34th FOCS, pp. 648\u2013658 (1993)","key":"37_CR10","DOI":"10.1109\/SFCS.1993.366822"},{"doi-asserted-by":"crossref","unstructured":"Dinitz, Y., Elkin, M., Solomon, S.: Shallow-low-light trees, and tight lower bounds for Euclidean spanners. In: Proc. of 49th FOCS, pp. 519\u2013528 (2008)","key":"37_CR11","DOI":"10.1109\/FOCS.2008.24"},{"doi-asserted-by":"crossref","unstructured":"Das, G., Heffernan, P.J., Narasimhan, G.: Optimally sparse spanners in 3-dimensional Euclidean space. In: Proc. of 9th SOCG, pp. 53\u201362 (1993)","key":"37_CR12","DOI":"10.1145\/160985.160998"},{"doi-asserted-by":"crossref","unstructured":"M.\u00a0Elkin and S.\u00a0Solomon. Optimal Euclidean spanners: really short, thin and lanky. In STOC, pages 645\u2013654, 2013.","key":"37_CR13","DOI":"10.1145\/2488608.2488691"},{"key":"37_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-642-32589-2_42","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M. Grigni","year":"2012","unstructured":"Grigni, M., Hung, H.-H.: Light spanners in bounded pathwidth graphs. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 467\u2013477. Springer, Heidelberg (2012)"},{"key":"37_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1007\/3-540-45022-X_73","volume-title":"Automata, Languages and Programming","author":"M. Grigni","year":"2000","unstructured":"Grigni, M.: Approximate TSP in graphs with forbidden minors. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 869\u2013877. Springer, Heidelberg (2000)"},{"unstructured":"Gottlieb, L., Solomon, S.: Light spanners for snowflake metrics. In: SoCG (to appear, 2014)","key":"37_CR16"},{"key":"37_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/978-3-540-87779-0_25","volume-title":"Distributed Computing","author":"I.A. Kanj","year":"2008","unstructured":"Kanj, I.A., Perkovi\u0107, L., Xia, G.: Computing lightweight spanners locally. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol.\u00a05218, pp. 365\u2013378. Springer, Heidelberg (2008)"},{"unstructured":"Kostic, D., Vahdat, A.: Latency versus cost optimizations in hierarchical overlay networks. Technical report, Duke University, CS-2001-04 (2002)","key":"37_CR18"},{"unstructured":"Mansour, Y., Peleg, D.: An approximation algorithm for minimum-cost network design. Technical report, Weizmann Institute of Science, Rehovot (1998)","key":"37_CR19"},{"doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)","key":"37_CR20","DOI":"10.1137\/1.9780898719772"},{"key":"37_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/11523468_22","volume-title":"Automata, Languages and Programming","author":"L. Roditty","year":"2005","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 261\u2013272. Springer, Heidelberg (2005)"},{"key":"37_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/978-3-540-30140-0_52","volume-title":"Algorithms \u2013 ESA 2004","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: On dynamic shortest paths problems. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 580\u2013591. Springer, Heidelberg (2004)"},{"issue":"3","key":"37_CR23","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1137\/S1052623497321432","volume":"11","author":"F.S. Salman","year":"2001","unstructured":"Salman, F.S., Cheriyan, J., Ravi, R., Subramanian, S.: Approximating the single-sink link-installation problem in network design. SIAM Journal on Optimization\u00a011(3), 595\u2013610 (2001)","journal-title":"SIAM Journal on Optimization"},{"issue":"6","key":"37_CR24","doi-asserted-by":"publisher","first-page":"1963","DOI":"10.1109\/TNET.2010.2053381","volume":"18","author":"H. Shpungin","year":"2010","unstructured":"Shpungin, H., Segal, M.: Near optimal multicriteria spanner constructions in wireless ad-hoc networks. IEEE\/ACM Transactions on Networking\u00a018(6), 1963\u20131976 (2010)","journal-title":"IEEE\/ACM Transactions on Networking"},{"issue":"3","key":"37_CR25","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1002\/net.10019","volume":"39","author":"B.Y. Wu","year":"2002","unstructured":"Wu, B.Y., Chao, K., Tang, C.Y.: Light graphs with small routing cost. Networks\u00a039(3), 130\u2013138 (2002)","journal-title":"Networks"}],"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-662-43948-7_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:31:09Z","timestamp":1746264669000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}