{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T22:12:00Z","timestamp":1778278320650,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642404498","type":"print"},{"value":"9783642404504","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_29","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"337-348","source":"Crossref","is-referenced-by-count":29,"title":["Dynamic Graphs in the Sliding-Window Model"],"prefix":"10.1007","author":[{"given":"Michael S.","family":"Crouch","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Stubbs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-02930-1_27","volume-title":"Automata, Languages and Programming","author":"K.J. Ahn","year":"2009","unstructured":"Ahn, K.J., Guha, S.: Graph sparsification in the semi-streaming model. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part II. LNCS, vol.\u00a05556, pp. 328\u2013338. Springer, Heidelberg (2009)"},{"key":"29_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: SODA, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"29_CR4","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"},{"key":"29_CR5","doi-asserted-by":"crossref","unstructured":"Arasu, A., Manku, G.S.: Approximate counts and quantiles over sliding windows. In: PODS, pp. 286\u2013296 (2004)","DOI":"10.1145\/1055558.1055598"},{"key":"29_CR6","doi-asserted-by":"crossref","unstructured":"Ayad, A., Naughton, J.F.: Static optimization of conjunctive queries with sliding windows over infinite streams. In: SIGMOD Conference, pp. 419\u2013430 (2004)","DOI":"10.1145\/1007568.1007616"},{"key":"29_CR7","unstructured":"Babcock, B., Datar, M., Motwani, R.: Sampling from a moving window over streaming data. In: SODA, pp. 633\u2013634 (2002)"},{"key":"29_CR8","doi-asserted-by":"crossref","unstructured":"Babcock, B., Datar, M., Motwani, R., O\u2019Callaghan, L.: Maintaining variance and k-medians over data stream windows. In: PODS, pp. 234\u2013243 (2003)","DOI":"10.1145\/773153.773176"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Baswana, S.: Streaming algorithm for graph spanners\u2014single pass and constant processing time per edge. Information Processing Letters (2008)","DOI":"10.1016\/j.ipl.2007.11.001"},{"key":"29_CR10","volume-title":"Extremal graph theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal graph theory. Academic Press, New York (1978)"},{"key":"29_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1007\/978-3-642-38768-5_56","volume-title":"Computing and Combinatorics","author":"V. Braverman","year":"2013","unstructured":"Braverman, V., Gelles, R., Ostrovsky, R.: How to catch \u21132-heavy-hitters on sliding windows. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol.\u00a07936, pp. 638\u2013650. Springer, Heidelberg (2013)"},{"key":"29_CR12","doi-asserted-by":"crossref","unstructured":"Braverman, V., Ostrovsky, R.: Smooth Histograms for Sliding Windows. In: 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 283\u2013293 (October 2007)","DOI":"10.1109\/FOCS.2007.55"},{"issue":"6","key":"29_CR13","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1137\/S0097539702403244","volume":"34","author":"B. Chazelle","year":"2005","unstructured":"Chazelle, B., Rubinfeld, R., Trevisan, L.: Approximating the minimum spanning tree weight in sublinear time. SIAM J. Comput.\u00a034(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"29_CR14","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M. Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining Stream Statistics over Sliding Windows. SIAM Journal on Computing\u00a031(6), 1794 (2002)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"29_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1921659.1921666","volume":"7","author":"M. Elkin","year":"2011","unstructured":"Elkin, M.: Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms\u00a07(2), 1\u201317 (2011)","journal-title":"ACM Transactions on Algorithms"},{"issue":"5","key":"29_CR16","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/265910.265914","volume":"44","author":"D. Eppstein","year":"1997","unstructured":"Eppstein, D., Galil, Z., Italiano, G., Nissenzweig, A.: Sparsificationa technique for speeding up dynamic graph algorithms. Journal of the ACM\u00a044(5), 669\u2013696 (1997)","journal-title":"Journal of the ACM"},{"issue":"3","key":"29_CR17","doi-asserted-by":"publisher","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L. Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model. SIAM Journal on Discrete Mathematics\u00a025(3), 1251\u20131265 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2-3","key":"29_CR18","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/j.tcs.2005.09.013","volume":"348","author":"J. Feigenbaum","year":"2005","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: On graph problems in a semi-streaming model. Theoretical Computer Science\u00a0348(2-3), 207\u2013216 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"29_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s00453-004-1105-2","volume":"41","author":"J. Feigenbaum","year":"2004","unstructured":"Feigenbaum, J., Kannan, S., Zhang, J.: Computing diameter in the streaming and sliding-window models. Algorithmica\u00a041(1), 25\u201341 (2004)","journal-title":"Algorithmica"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Fung, W.S., Hariharan, R., Harvey, N.J.A., Panigrahi, D.: A general framework for graph sparsification. In: STOC, pp. 71\u201380 (2011)","DOI":"10.1145\/1993636.1993647"},{"key":"29_CR21","unstructured":"Goel, A., Kapralov, M., Post, I.: Single pass sparsification in the streaming model with edge deletions. CoRR, abs\/1203.4900 (2012)"},{"issue":"4","key":"29_CR22","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1145\/320211.320215","volume":"46","author":"M.R. Henzinger","year":"1999","unstructured":"Henzinger, M.R., King, V.: Randomized fully dynamic graph algorithms with polylogarithmic time per operation. J. ACM\u00a046(4), 502\u2013516 (1999)","journal-title":"J. ACM"},{"issue":"4","key":"29_CR23","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"29_CR24","doi-asserted-by":"crossref","unstructured":"Italiano, G., Eppstein, D., Galil, Z.: Dynamic graph algorithms. In: Algorithms and Theory of Computation Handbook. CRC Press (1999)","DOI":"10.1201\/9781420049503-c9"},{"key":"29_CR25","doi-asserted-by":"crossref","unstructured":"Kapralov, M.: Better bounds for matchings in the streaming model. In: SODA, pp. 1679\u20131697 (2013)","DOI":"10.1137\/1.9781611973105.121"},{"key":"29_CR26","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity, vol.\u00a02006. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"29_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/11538462_15","volume-title":"Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques","author":"A. McGregor","year":"2005","unstructured":"McGregor, A.: Finding graph matchings in data streams. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol.\u00a03624, pp. 170\u2013181. Springer, Heidelberg (2005)"},{"key":"29_CR28","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. Tarjan","year":"1983","unstructured":"Tarjan, R.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)"},{"key":"29_CR29","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Near-optimal fully-dynamic graph connectivity. In: STOC, pp. 343\u2013350 (2000)","DOI":"10.1145\/335305.335345"},{"issue":"1-2","key":"29_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-010-9438-5","volume":"62","author":"M. Zelke","year":"2012","unstructured":"Zelke, M.: Weighted matching in the semi-streaming model. Algorithmica\u00a062(1-2), 1\u201320 (2012)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T16:58:41Z","timestamp":1558025921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}