{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:52:49Z","timestamp":1725558769811},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642140303"},{"type":"electronic","value":"9783642140310"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14031-0_19","type":"book-chapter","created":{"date-parts":[[2010,6,28]],"date-time":"2010-06-28T09:50:06Z","timestamp":1277718606000},"page":"160-172","source":"Crossref","is-referenced-by-count":0,"title":["Computing Graph Spanners in Small Memory: Fault-Tolerance and Streaming"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Ausiello","sequence":"first","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":[{"issue":"2","key":"19_CR1","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s00453-008-9216-9","volume":"55","author":"G. Ausiello","year":"2009","unstructured":"Ausiello, G., Demetrescu, C., Franciosa, P.G., Italiano, G.F., Ribichini, A.: Graph spanners in the streaming model: An experimental study. Algorithmica\u00a055(2), 346\u2013374 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"19_CR2","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":"36","key":"19_CR3","doi-asserted-by":"publisher","first-page":"3406","DOI":"10.1016\/j.tcs.2008.04.022","volume":"410","author":"G. Ausiello","year":"2009","unstructured":"Ausiello, G., Franciosa, P.G., Italiano, G.F.: Small stretch (\u03b1, \u03b2)-spanners in the streaming model. Theoretical Computer Science\u00a0410(36), 3406\u20133413 (2009)","journal-title":"Theoretical Computer Science"},{"key":"19_CR4","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)"},{"issue":"3","key":"19_CR5","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.ipl.2007.11.001","volume":"106","author":"S. Baswana","year":"2008","unstructured":"Baswana, S.: Streaming algorithm for graph spanners - single pass and constant processing time per edge. Inf. Process. Lett.\u00a0106(3), 110\u2013114 (2008)","journal-title":"Inf. Process. Lett."},{"key":"19_CR6","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: New constructions of (\u03b1, \u03b2)-spanners and purely additive spanners. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905), pp. 672\u2013681 (2005)"},{"key":"19_CR7","unstructured":"Baswana, S., Sarkar, S.: Fully dynamic algorithm for graph spanners with poly-logarithmic update time. In: Proc. of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201908), pp. 1125\u20131134 (2008)"},{"issue":"4","key":"19_CR8","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 and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms\u00a030(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"19_CR9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","volume":"1","author":"J.L. Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: Static-to-dynamic transformation. J. Algorithms\u00a01(4), 301\u2013358 (1980)","journal-title":"J. Algorithms"},{"key":"19_CR10","doi-asserted-by":"crossref","unstructured":"Chechik, S., Langberg, M., Peleg, D., Roditty, L.: Fault-tolerant spanners for general graphs. In: Proc. of 41st Annual ACM Symposium on Theory of Computing (STOC\u201909), pp. 435\u2013444 (2009)","DOI":"10.1145\/1536414.1536475"},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM Journal on Computing\u00a028(1), 210\u2013236 (1998)","journal-title":"SIAM Journal on Computing"},{"key":"19_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"716","DOI":"10.1007\/978-3-540-73420-8_62","volume-title":"Automata, Languages and Programming","author":"M. Elkin","year":"2007","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 716\u2013727. Springer, Heidelberg (2007)"},{"issue":"5","key":"19_CR13","doi-asserted-by":"publisher","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\u2009+\u2009\u03b5, \u03b2)-spanners in the distributed and streaming models. Distributed Computing\u00a018(5), 375\u2013385 (2006)","journal-title":"Distributed Computing"},{"key":"19_CR14","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905), pp. 745\u2013754 (2005)"},{"key":"19_CR15","doi-asserted-by":"publisher","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\u00a023, 343\u2013364 (1993)","journal-title":"Networks"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"J. Ian Munro","year":"1980","unstructured":"Ian Munro, J., Paterson, M.: Selection and sorting with limited storage. Theor. Comput. Sci.\u00a012, 315\u2013323 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"19_CR17","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. Journal of Graph Theory\u00a013, 99\u2013116 (1989)","journal-title":"Journal of Graph Theory"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/978-3-540-73420-8_9","volume-title":"Automata, Languages and Programming","author":"S. Pettie","year":"2007","unstructured":"Pettie, S.: Low distortion spanners. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 78\u201389. Springer, Heidelberg (2007)"},{"key":"19_CR19","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)"},{"key":"19_CR20","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proc. of 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201906), pp. 802\u2013809 (2006)","DOI":"10.1145\/1109557.1109645"},{"issue":"2","key":"19_CR21","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1006\/inco.1997.2641","volume":"136","author":"G. Venkatesan","year":"1997","unstructured":"Venkatesan, G., Rotics, U., Madanlal, M.S., Makowsky, J.A., Pandu Rangan, C.: Restrictions of minimum spanner problems. Information and Computation\u00a0136(2), 143\u2013164 (1997)","journal-title":"Information and Computation"},{"issue":"2","key":"19_CR22","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"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14031-0_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:16:24Z","timestamp":1619784984000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14031-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642140303","9783642140310"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14031-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}