{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:16:30Z","timestamp":1763468190273,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439500"},{"type":"electronic","value":"9783662439517"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43951-7_49","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T08:37:49Z","timestamp":1402475869000},"page":"608-619","source":"Crossref","is-referenced-by-count":11,"title":["Bypassing Erd\u0151s\u2019 Girth Conjecture: Hybrid Stretch and Sourcewise Spanners"],"prefix":"10.1007","author":[{"given":"Merav","family":"Parter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Agarwal, R., Godfrey, P.B., Har-Peled, S.: Approximate distance queries and compact routing in sparse graphs. In: Proc. INFOCOM (2011)","key":"49_CR1","DOI":"10.1109\/INFCOM.2011.5934973"},{"issue":"4","key":"49_CR2","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."},{"unstructured":"Alon, N., Spencer, J.H.: The probabilistic method. Wiley, Chichester (1992)","key":"49_CR3"},{"issue":"1","key":"49_CR4","first-page":"81","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. Networks\u00a09(1), 81\u2013100 (1993)","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (\u03b1, \u03b2)-spanners. ACM Trans. Algo.\u00a07, A.5 (2010)","key":"49_CR5","DOI":"10.1145\/1868237.1868242"},{"issue":"4","key":"49_CR6","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S. Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple Linear Time Randomized Algorithm for Computing Sparse Spanners in Weighted Graphs. Random Structures and Algorithms\u00a030(4), 532\u2013563 (2007)","journal-title":"Random Structures and Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proc. FOCS, pp. 591\u2013602 (2006)","key":"49_CR7","DOI":"10.1109\/FOCS.2006.29"},{"issue":"4","key":"49_CR8","doi-asserted-by":"publisher","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) time. ACM Transactions on Algorithms (TALG)\u00a02(4), 557\u2013577 (2006)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"4","key":"49_CR9","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/S0895480103431046","volume":"19","author":"B. Bollob\u00e1s","year":"2005","unstructured":"Bollob\u00e1s, B., Coppersmith, D., Elkin, M.: Sparse distance preservers and additive spanners. SIAM Journal on Discrete Mathematics\u00a019(4), 1029\u20131055 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"49_CR10","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D. Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM Journal on Discrete Mathematics\u00a020(2), 463\u2013501 (2006)","journal-title":"SIAM Journal on Discrete Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Chechik, S.: New Additive Spanners. In: Proc. SODA, vol.\u00a029(5), pp. 498\u2013512 (2013)","key":"49_CR11","DOI":"10.1137\/1.9781611973105.36"},{"unstructured":"Cygan, M., Grandoni, F., Kavitha, T.: On Pairwise Spanners. In: Proc. STACS, pp. 209\u2013220 (2013)","key":"49_CR12"},{"issue":"2","key":"49_CR13","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. Distributed Computing\u00a016(2), 111\u2013120 (2003)","journal-title":"Distributed Computing"},{"issue":"5","key":"49_CR14","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 on Computing\u00a029(5), 1740\u20131759 (2000)","journal-title":"SIAM on Computing"},{"issue":"3","key":"49_CR15","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M. Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: (1\u2009+\u2009\u03b5, \u03b2)-Spanner Constructions for General Graphs. SIAM Journal on Computing\u00a033(3), 608\u2013631 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"49_CR16","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 (TALG)\u00a01(2), 283\u2013323 (2005)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"doi-asserted-by":"crossref","unstructured":"Elkin, M., Emek, Y., Spielman, D.A., Teng, S.H.: Lower stretch spanning trees. In: Proc. STOC, pp. 494\u2013503 (2005)","key":"49_CR17","DOI":"10.1145\/1060590.1060665"},{"unstructured":"Erd\u0151s, P.: Extremal problems in graph theory. In: Proc. Symp. Theory of Graphs and its Applications, pp. 29\u201336 (1963)","key":"49_CR18"},{"doi-asserted-by":"crossref","unstructured":"Kapralov, M., Panigrahy, R.: Spectral sparsification via random spanners. In: ITCS (2012)","key":"49_CR19","DOI":"10.1145\/2090236.2090267"},{"key":"49_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1007\/978-3-642-39206-1_51","volume-title":"Automata, Languages, and Programming","author":"T. Kavitha","year":"2013","unstructured":"Kavitha, T., Varma, N.M.: Small Stretch Pairwise Spanners. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol.\u00a07965, pp. 601\u2013612. Springer, Heidelberg (2013)"},{"issue":"4","key":"49_CR21","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.C.: Additive graph spanners. Networks\u00a023(4), 343\u2013363 (1993)","journal-title":"Networks"},{"doi-asserted-by":"crossref","unstructured":"Mendel, M., Naor, A.: Ramsey partitions and proximity data structures. In: FOCS, vol.\u00a023(4), pp. 109\u2013118 (2006)","key":"49_CR22","DOI":"10.1109\/FOCS.2006.65"},{"doi-asserted-by":"crossref","unstructured":"Parter, M.: Bypassing Erd\u0151s\u2019 Girth Conjecture: Hybrid Stretch and Sourcewise Spanners (2014), http:\/\/arxiv.org\/abs\/1404.6835","key":"49_CR23","DOI":"10.1007\/978-3-662-43951-7_49"},{"doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Roditty, L.: Distance oracles beyond the Thorup-Zwick bound. In: FOCS, pp. 815\u2013823 (2010)","key":"49_CR24","DOI":"10.1109\/FOCS.2010.83"},{"issue":"1","key":"49_CR25","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"12","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Schaffer, A.A.: Graph spanners. Journal of Graph Theory\u00a012(1), 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"issue":"4","key":"49_CR26","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM Journal on Computing\u00a018(4), 740\u2013747 (1989)","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","key":"49_CR27","DOI":"10.1137\/1.9780898719772"},{"doi-asserted-by":"crossref","unstructured":"Pettie, S.: Low distortion spanners. ACM Transactions on Algorithms (TALG)\u00a06(1) (2009)","key":"49_CR28","DOI":"10.1145\/1644015.1644022"},{"key":"49_CR29","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)"},{"issue":"3","key":"49_CR30","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1145\/316542.316548","volume":"46","author":"M. Thorup","year":"1999","unstructured":"Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM (JACM)\u00a046(3), 362\u2013394 (1999)","journal-title":"Journal of the ACM (JACM)"},{"issue":"1","key":"49_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M. Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. Journal of the ACM (JACM)\u00a052(1), 1\u201324 (2005)","journal-title":"Journal of the ACM (JACM)"},{"doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: SODA, pp. 802\u2013809 (2006)","key":"49_CR32","DOI":"10.1145\/1109557.1109645"},{"doi-asserted-by":"crossref","unstructured":"Wenger, R.: Extremal graphs with no C4\u2019s, C6\u2019s, or C10\u2019s. Journal of Combinatorial Theory, 113\u2013116 (1991)","key":"49_CR33","DOI":"10.1016\/0095-8956(91)90097-4"},{"doi-asserted-by":"crossref","unstructured":"Woodruff, D.P.: Lower bounds for additive spanners, emulators, and more. In: Proc. 47th Symp. on Foundations of Computer Science, pp. 389\u2013398 (2006)","key":"49_CR34","DOI":"10.1109\/FOCS.2006.45"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43951-7_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T09:23:33Z","timestamp":1746264213000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-43951-7_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439500","9783662439517"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43951-7_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}