{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,12]],"date-time":"2025-05-12T18:42:41Z","timestamp":1747075361667},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,8,29]],"date-time":"2008-08-29T00:00:00Z","timestamp":1219968000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2009,10]]},"DOI":"10.1007\/s00453-008-9216-9","type":"journal-article","created":{"date-parts":[[2008,8,28]],"date-time":"2008-08-28T16:56:29Z","timestamp":1219942589000},"page":"346-374","source":"Crossref","is-referenced-by-count":9,"title":["Graph Spanners in the Streaming Model: An\u00a0Experimental Study"],"prefix":"10.1007","volume":"55","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","published-online":{"date-parts":[[2008,8,29]]},"reference":[{"key":"9216_CR1","unstructured":"Experimental package. Available at http:\/\/www.dis.uniroma1.it\/~ribichini\/spanner\/"},{"key":"9216_CR2","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Datar, M., Rajagopalan, S., Ruhl, M.: On the streaming model augmented with sorting primitive. In: Proc. FOCS\u201904, pp. 540\u2013549 (2004)","DOI":"10.1109\/FOCS.2004.48"},{"key":"9216_CR3","doi-asserted-by":"crossref","first-page":"4947","DOI":"10.1242\/jcs.02714","volume":"118","author":"R. Albert","year":"2005","unstructured":"Albert, R.: Scale-free networks in cell biology. J. Cell Sci. 118, 4947\u20134957 (2005)","journal-title":"J. Cell Sci."},{"key":"9216_CR4","doi-asserted-by":"crossref","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 Comput. Geom. 9, 81\u2013100 (1993)","journal-title":"Discrete Comput. Geom."},{"key":"9216_CR5","series-title":"LNCS","first-page":"605","volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track","author":"G. Ausiello","year":"2007","unstructured":"Ausiello, G., Demetrescu, C., Franciosa, P.G., Italiano, G.F., Ribichini, A.: Small stretch spanners in the streaming model: New algorithms and experiments. In: Proceedings of the 15th Annual European Symposium on Algorithms (ESA 2007), Engineering and Applications Track, Eilat, Israel, 8\u201310 October 2007. LNCS, vol. 4698, pp. 605\u2013617. Springer, Berlin (2007)"},{"issue":"2","key":"9216_CR6","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. J. Graph Algorithms Appl. 10(2), 365\u2013385 (2006)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"9216_CR7","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B. Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804\u2013823 (1985)","journal-title":"J. ACM"},{"key":"9216_CR8","doi-asserted-by":"crossref","unstructured":"Baswana, S.: Dynamic algorithms for graph spanners. In: Proc. ESA\u201906, pp. 76\u201387 (2006)","DOI":"10.1007\/11841036_10"},{"key":"9216_CR9","unstructured":"Baswana, S.: Faster streaming algorithms for graph spanners (2006). http:\/\/www.citebase.org\/abstract?id=oai:arXiv.org:cs\/0611023"},{"key":"9216_CR10","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1, \u03b2)-spanners and purely additive spanners. In: Proc. SODA\u201905, pp. 672\u2013681 (2005)"},{"key":"9216_CR11","doi-asserted-by":"crossref","unstructured":"Baswana, S., Sen, S.: A simple linear time algorithm for computing (2k\u22121)-spanner of O(n 1+1\/k ) size for weighted graphs. In: Proc. ICALP\u201903, pp. 384\u2013396 (2003)","DOI":"10.1007\/3-540-45061-0_32"},{"key":"9216_CR12","doi-asserted-by":"crossref","unstructured":"Buriol, L., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Proceedings of the 25th ACM Symposium on Principles of Database Systems (PODS\u201906), pp. 253\u2013262 (2006)","DOI":"10.1145\/1142351.1142388"},{"issue":"2","key":"9216_CR13","first-page":"187","volume":"48","author":"L. Cai","year":"1994","unstructured":"Cai, L.: NP-completeness of minimum spanner problems. Discrete Appl. Math. Combin. Oper. Res. Comput. Sci. 48(2), 187\u2013194 (1994)","journal-title":"Discrete Appl. Math. Combin. Oper. Res. Comput. Sci."},{"key":"9216_CR14","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1142\/S0129626493000484","volume":"3","author":"L. Cai","year":"1993","unstructured":"Cai, L., Keil, J.M.: Degree-bounded spanners. Parallel Process. Lett. 3, 457\u2013468 (1993)","journal-title":"Parallel Process. Lett."},{"key":"9216_CR15","doi-asserted-by":"crossref","unstructured":"Chakrabarti, D., Zhan, Y., Faloutsos, C.: R-MAT: A recursive model for graph mining. In: Proceedings of the 4th SIAM International Conference on Data Mining (2004)","DOI":"10.1137\/1.9781611972740.43"},{"issue":"2","key":"9216_CR16","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 39(2), 205\u2013219 (1989)","journal-title":"J. Comput. Syst. Sci."},{"key":"9216_CR17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-51859-2_15","volume-title":"Proc. Int. Symp. on Optimal Algorithms","author":"G. Das","year":"1989","unstructured":"Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: Proc. Int. Symp. on Optimal Algorithms. LNCS, vol. 401, pp. 168\u2013192. Springer, Berlin (1989)"},{"key":"9216_CR18","doi-asserted-by":"crossref","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 Comput. Geom. 5, 399\u2013407 (1990)","journal-title":"Discrete Comput. Geom."},{"key":"9216_CR19","doi-asserted-by":"crossref","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: Proceedings of the 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), Wroclaw, Poland, pp. 716\u2013727, 9\u201313 July 2007","DOI":"10.1007\/978-3-540-73420-8_62"},{"issue":"5","key":"9216_CR20","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+\u03b5,\u03b2)-spanners in the distributed and streaming models. Distrib. Comput. 18(5), 375\u2013385 (2006)","journal-title":"Distrib. Comput."},{"key":"9216_CR21","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. Publ. Math. Debrecen 6, 290\u2013291 (1959)","journal-title":"Publ. Math. Debrecen"},{"key":"9216_CR22","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/316188.316229","volume-title":"SIGCOMM \u201999: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication","author":"M. Faloutsos","year":"1999","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: SIGCOMM \u201999: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, New York, NY, USA, pp. 251\u2013262. ACM Press, New York (1999)"},{"key":"9216_CR23","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: Proc. SODA\u201905, pp. 745\u2013754 (2005)"},{"key":"9216_CR24","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":"9216_CR25","first-page":"122","volume":"23","author":"A.L. Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.: Grid spanners. Networks 23, 122\u2013133 (1993)","journal-title":"Networks"},{"key":"9216_CR26","doi-asserted-by":"crossref","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 13, 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"4","key":"9216_CR27","doi-asserted-by":"crossref","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 J. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"key":"9216_CR28","first-page":"1","volume":"25","author":"D. Richards","year":"1995","unstructured":"Richards, D., Liestman, A.L.: Degree-constrained pyramid spanners. JPDC: J. Parallel Distrib. Comput. 25, 1\u20136 (1995)","journal-title":"JPDC: J. Parallel Distrib. Comput."},{"key":"9216_CR29","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proc. ICALP\u201905, pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"9216_CR30","unstructured":"Zwick, U.: Personal communication"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9216-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9216-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9216-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,19]],"date-time":"2023-05-19T19:42:37Z","timestamp":1684525357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9216-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,29]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["9216"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9216-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,29]]}}}