{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:51:22Z","timestamp":1764557482407,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T00:00:00Z","timestamp":1537833600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Shanghai Science and Technology Commission","award":["17JC1420200"],"award-info":[{"award-number":["17JC1420200"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["307696"],"award-info":[{"award-number":["307696"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Australian Research Council Discovery Grant","award":["DP150102728"],"award-info":[{"award-number":["DP150102728"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s00453-018-0520-8","type":"journal-article","created":{"date-parts":[[2018,9,25]],"date-time":"2018-09-25T10:58:22Z","timestamp":1537873102000},"page":"1965-1987","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Graph Stream Algorithms in o(n) Space"],"prefix":"10.1007","volume":"81","author":[{"given":"Zengfeng","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2700-5699","authenticated-orcid":false,"given":"Pan","family":"Peng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,9,25]]},"reference":[{"key":"520_CR1","unstructured":"Ahn, K.J., Cormode, G., Guha, S., McGregor, A., Wirth, A.: Correlation clustering in data streams. In: Proceedings of the 32nd International Conference on Machine Learning, ICML, pp. 6\u201311 (2015)"},{"key":"520_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 459\u2013467. SIAM, Philadelphia (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"520_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st Symposium on Principles of Database Systems, pp. 5\u201314. ACM, New York (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"520_CR4","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 20\u201329. ACM, New York (1996)","DOI":"10.1145\/237814.237823"},{"key":"520_CR5","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Maximum matchings in dynamic graph streams and the simultaneous communication model. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201916, pp. 1345\u20131364. SIAM, Philadelphia (2016)","DOI":"10.1137\/1.9781611974331.ch93"},{"key":"520_CR6","doi-asserted-by":"crossref","unstructured":"Bhattacharya, S., Henzinger, M., Nanongkai, D., Tsourakakis, C.E.: Space-and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In: ACM Symposium on Theory of Computing (2015)","DOI":"10.1145\/2746539.2746592"},{"key":"520_CR7","doi-asserted-by":"crossref","unstructured":"Bury, M., Schwiegelshohn, C.: Sublinear estimation of weighted matchings in dynamic data streams. ESA (2015)","DOI":"10.1007\/978-3-662-48350-3_23"},{"issue":"6","key":"520_CR8","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. 34(6), 1370\u20131379 (2005)","journal-title":"SIAM J. Comput."},{"key":"520_CR9","unstructured":"Chitnis, R., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to dynamic graph streams. SODA (2016)"},{"key":"520_CR10","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Cormode, G., Hajiaghayi, M., Monemizadeh, M.: Parameterized streaming: maximal matching and vertex cover. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1234\u20131251. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.82"},{"issue":"1","key":"520_CR11","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S0097539703435297","volume":"35","author":"A Czumaj","year":"2005","unstructured":"Czumaj, A., Erg\u00fcn, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.: Approximating the weight of the euclidean minimum spanning tree in sublinear time. SIAM J. Comput. 35(1), 91\u2013109 (2005)","journal-title":"SIAM J. Comput."},{"key":"520_CR12","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Monemizadeh, M., Onak, K., Sohler, C.: Planar graphs: random walks and bipartiteness testing. In: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pp. 423\u2013432. IEEE (2011)","DOI":"10.1109\/FOCS.2011.69"},{"issue":"3","key":"520_CR13","doi-asserted-by":"publisher","first-page":"904","DOI":"10.1137\/060672121","volume":"39","author":"A Czumaj","year":"2009","unstructured":"Czumaj, A., Sohler, C.: Estimating the weight of metric minimum spanning trees in sublinear time. SIAM J. Comput. 39(3), 904\u2013922 (2009)","journal-title":"SIAM J. Comput."},{"key":"520_CR14","doi-asserted-by":"crossref","unstructured":"Esfandiari, H., Hajiaghayi, M., Woodruff, D.P.: Brief announcement: applications of uniform sampling: densest subgraph and beyond. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016, pp. 397\u2013399 (2016)","DOI":"10.1145\/2935764.2935813"},{"key":"520_CR15","doi-asserted-by":"crossref","unstructured":"Esfandiari, H., Hajiaghayi, M.T., Liaghat, V., Monemizadeh, M., Onak, K.: Streaming algorithms for estimating the matching size in planar graphs and beyond. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1217\u20131233. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.81"},{"key":"520_CR16","doi-asserted-by":"crossref","unstructured":"Fafianie, S., Kratsch, S.: Streaming kernelization. In: Mathematical Foundations of Computer Science 2014, pp. 275\u2013286. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-44465-8_24"},{"issue":"2","key":"520_CR17","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. Theor. Comput. Sci. 348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"520_CR18","doi-asserted-by":"publisher","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J Feigenbaum","year":"2008","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM J. Comput. 38(5), 1709\u20131727 (2008)","journal-title":"SIAM J. Comput."},{"key":"520_CR19","doi-asserted-by":"crossref","unstructured":"Frahling, G., Indyk, P., Sohler, C.: Sampling in dynamic data streams and applications. In: Proceedings of the Twenty-First Annual Symposium on Computational Geometry, pp. 142\u2013149. ACM, New York (2005)","DOI":"10.1145\/1064092.1064116"},{"key":"520_CR20","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Introduction to testing graph properties. In: Property Testing, pp. 105\u2013141. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-16367-8_7"},{"issue":"4","key":"520_CR21","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. J. ACM 45(4), 653\u2013750 (1998)","journal-title":"J. ACM"},{"key":"520_CR22","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1007\/s00453-001-0078-7","volume":"32","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Ron, D.: Property testing in bounded degree graphs. Algorithmica 32, 302\u2013343 (2002)","journal-title":"Algorithmica"},{"key":"520_CR23","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hyperedge connectivity in dynamic graph streams. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems, pp. 241\u2013247. ACM, New York (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"520_CR24","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: External Memory Algorithms, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, May 20\u201322, pp. 107\u2013118 (1998)","DOI":"10.1090\/dimacs\/050\/05"},{"key":"520_CR25","unstructured":"Jowhari, H.: Estimating the number of connected components in graph streams. Personal Communication"},{"key":"520_CR26","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Approximating matching size from random streams. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 734\u2013751. SIAM, Philadelphia (2014)","DOI":"10.1137\/1.9781611973402.55"},{"key":"520_CR27","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Streaming lower bounds for approximating max-cut. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1263\u20131282. SIAM, Philadelphia (2015)","DOI":"10.1137\/1.9781611973730.84"},{"key":"520_CR28","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pp. 561\u2013570. IEEE (2014)","DOI":"10.1109\/FOCS.2014.66"},{"key":"520_CR29","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.: Spanners and sparsifiers in dynamic streams. In: Proceedings of the 2014 ACM symposium on Principles of distributed computing, pp. 272\u2013281. ACM, New York (2014)","DOI":"10.1145\/2611462.2611497"},{"key":"520_CR30","doi-asserted-by":"crossref","unstructured":"Kogan, D., Krauthgamer, R.: Sketching cuts in graphs and hypergraphs. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp. 367\u2013376. ACM, New York (2015)","DOI":"10.1145\/2688073.2688093"},{"key":"520_CR31","doi-asserted-by":"crossref","unstructured":"Konrad, C.: Maximum matching in turnstile streams. ESA (2015)","DOI":"10.1007\/978-3-662-48350-3_70"},{"issue":"1","key":"520_CR32","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. ACM SIGMOD Rec. 43(1), 9\u201320 (2014)","journal-title":"ACM SIGMOD Rec."},{"key":"520_CR33","doi-asserted-by":"crossref","unstructured":"McGregor, A., Tench, D., Vorotnikova, S., Vu, H.T.: Densest subgraph in dynamic graph streams. MFCS (2015)","DOI":"10.1007\/978-3-662-48054-0_39"},{"issue":"2","key":"520_CR34","first-page":"117","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"45","key":"520_CR35","doi-asserted-by":"publisher","first-page":"6390","DOI":"10.1016\/j.tcs.2011.06.038","volume":"412","author":"Y Orenstein","year":"2011","unstructured":"Orenstein, Y., Ron, D.: Testing eulerianity and connectivity in directed sparse graphs. Theor. Comput. Sci. 412(45), 6390\u20136408 (2011)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"520_CR36","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1002\/rsa.10013","volume":"20","author":"M Parnas","year":"2002","unstructured":"Parnas, M., Ron, D.: Testing the diameter of graphs. Random Struct. Algorithms 20(2), 165\u2013183 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"520_CR37","doi-asserted-by":"crossref","unstructured":"Peng, P., Sohler, C.: Estimating graph parameters from random order streams. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2449\u20132466. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.157"},{"key":"520_CR38","doi-asserted-by":"crossref","unstructured":"Price, E.: Efficient sketches for the set query problem. In: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 41\u201356. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.4"},{"issue":"2","key":"520_CR39","first-page":"73","volume":"5","author":"D Ron","year":"2010","unstructured":"Ron, D.: Algorithmic and analysis techniques in property testing: foundations and trends \n                    \n                      \n                    \n                    $$\\textregistered $$\n                    \n                      \n                        \u00ae\n                      \n                    \n                  . Theor. Comput. Sci. 5(2), 73\u2013205 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"520_CR40","doi-asserted-by":"publisher","first-page":"1562","DOI":"10.1137\/100791075","volume":"25","author":"R Rubinfeld","year":"2011","unstructured":"Rubinfeld, R., Shapira, A.: Sublinear time algorithms. SIAM J. Discrete Math. 25(4), 1562\u20131588 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"520_CR41","unstructured":"Sun, X., Woodruff, D.P.: Tight bounds for graph problems in insertion streams. In: The 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u20192015) (2015)"},{"key":"520_CR42","doi-asserted-by":"crossref","unstructured":"Verbin, E., Yu, W.: The streaming complexity of cycle counting, sorting by reversals, and other problems. In: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 11\u201325. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.2"},{"key":"520_CR43","doi-asserted-by":"crossref","unstructured":"Yoshida, Y., Ito, H.: Property testing on k-vertex-connectivity of graphs. In: Automata, Languages and Programming, pp. 539\u2013550. Springer, Berlin (2008)","DOI":"10.1007\/978-3-540-70575-8_44"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0520-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0520-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0520-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T03:26:45Z","timestamp":1569382005000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0520-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,25]]},"references-count":43,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["520"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0520-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,9,25]]},"assertion":[{"value":"26 October 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}