{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:16:55Z","timestamp":1725491815596},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755197"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75520-3_54","type":"book-chapter","created":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T03:46:33Z","timestamp":1189741593000},"page":"605-617","source":"Crossref","is-referenced-by-count":1,"title":["Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","affiliation":[]},{"given":"Camil","family":"Demetrescu","sequence":"additional","affiliation":[]},{"given":"Paolo G.","family":"Franciosa","sequence":"additional","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Ribichini","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"54_CR1","unstructured":"Experimental package, See: http:\/\/www.dis.uniroma1.it\/~ribichini\/spanner\/"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with sorting primitive. In: FOCS 2004, pp. 540\u2013549 (2004)","DOI":"10.1109\/FOCS.2004.48"},{"key":"54_CR3","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1007\/BF02189308","volume":"9","author":"I. Althofer","year":"1993","unstructured":"Althofer, 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"},{"issue":"2","key":"54_CR4","doi-asserted-by":"crossref","first-page":"365","DOI":"10.7155\/jgaa.00133","volume":"10","author":"G. Ausiello","year":"2006","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F.: Small stretch spanners on dynamic graphs. Journal of Graph Algorithms and Applications\u00a010(2), 365\u2013385 (2006)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"4","key":"54_CR5","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchroniz. JACM\u00a032(4), 804\u2013823 (1985)","journal-title":"JACM"},{"key":"54_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/11841036_10","volume-title":"Algorithms \u2013 ESA 2006","author":"S. Baswana","year":"2006","unstructured":"Baswana, S.: Dynamic algorithms for graph spanners. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 76\u201387. Springer, Heidelberg (2006)"},{"key":"54_CR7","unstructured":"Baswana, S.: Faster streaming algorithms for graph spanners: (2006), http:\/\/www.citebase.org\/abstract?id=oaiarXiv.org:cs\/0611023"},{"key":"54_CR8","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1, \u03b2)-spanners and purely additive spanners. In: SODA 2005, pp. 672\u2013681 (2005)"},{"key":"54_CR9","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 (2k\u2009\u2212\u20091)-spanner of O(n 1\u2009+\u20091\/k ) size for 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)"},{"issue":"2","key":"54_CR10","first-page":"187","volume":"48","author":"L. Cai","year":"1994","unstructured":"Cai, L.: NP-completeness of minimum spanner problems. Discr. Appl. Math. and Combinat. Operations Res. and Comp. Science\u00a048(2), 187\u2013194 (1994)","journal-title":"Discr. Appl. Math. and Combinat. Operations Res. and Comp. Science"},{"key":"54_CR11","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1142\/S0129626493000484","volume":"3","author":"L. Cai","year":"1993","unstructured":"Cai, L., Keil, J.M.: Degree-bounded spanners. Par. Proc. Lett.\u00a03, 457\u2013468 (1993)","journal-title":"Par. Proc. Lett."},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: A recursive model for graph mining. In: 4th SIAM International Conference on Data Mining (2004)","DOI":"10.1137\/1.9781611972740.43"},{"issue":"2","key":"54_CR13","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0022-0000(89)90044-5","volume":"39","author":"L.P. Chew","year":"1989","unstructured":"Chew, L.P.: There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences\u00a039(2), 205\u2013219 (1989)","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Optimal Algorithms","author":"G. Das","year":"1989","unstructured":"Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol.\u00a0401, pp. 168\u2013192. Springer, Heidelberg (1989)"},{"key":"54_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/BF02187801","volume":"5","author":"D. Dobkin","year":"1990","unstructured":"Dobkin, D., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry\u00a05, 399\u2013407 (1990)","journal-title":"Discrete & Computational Geometry"},{"key":"54_CR16","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs. P. Math. Debrecen\u00a06, 290\u2013291 (1959)","journal-title":"P. Math. Debrecen"},{"key":"54_CR17","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: SODA 2005, pp. 745\u2013754 (2005)"},{"key":"54_CR18","first-page":"122","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.: Grid spanners. Networks\u00a023, 122\u2013133 (1993)","journal-title":"Networks"},{"key":"54_CR19","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.: Additive graph spanners. Networks, 23, 343\u2013364 (1993)","journal-title":"Networks"},{"key":"54_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"Peleg, D., Sh\u00e4ffer, A.: Graph spanners. J. Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"4","key":"54_CR21","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"},{"key":"54_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/jpdc.1995.1024","volume":"25","author":"D. Richards","year":"1995","unstructured":"Richards, D., Liestman, A.L.: Degree-constrained pyramid spanners. JPDC: Journal of Parallel and Distributed Computing\u00a025, 1\u20136 (1995)","journal-title":"JPDC: Journal of Parallel and Distributed Computing"},{"key":"54_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"2","key":"54_CR24","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/384192.384193","volume":"33","author":"J.S. Vitter","year":"2001","unstructured":"Vitter, J.S.: External memory algorithms and data structures: dealing with massive data. ACM Computing Surveys\u00a033(2), 209\u2013271 (2001)","journal-title":"ACM Computing Surveys"},{"key":"54_CR25","unstructured":"Zwick, U.: Personal communication"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75520-3_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T04:13:14Z","timestamp":1684037594000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75520-3_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540755197"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75520-3_54","relation":{},"subject":[]}}