{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T04:24:09Z","timestamp":1780547049223,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662480533","type":"print"},{"value":"9783662480540","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_39","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T07:57:29Z","timestamp":1439193449000},"page":"472-482","source":"Crossref","is-referenced-by-count":35,"title":["Densest Subgraph in Dynamic Graph Streams"],"prefix":"10.1007","author":[{"given":"Andrew","family":"McGregor","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Tench","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sofya","family":"Vorotnikova","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hoa T.","family":"Vu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"39_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 2015, Lille, France, July 6\u201311, 2015 (2015)"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, pp. 459\u2013467 (2012)","DOI":"10.1137\/1.9781611973099.40"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pp. 5\u201314 (2012)","DOI":"10.1145\/2213556.2213560"},{"key":"39_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-40328-6_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"KJ Ahn","year":"2013","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Spectral sparsification in dynamic graph streams. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 1\u201310. Springer, Heidelberg (2013)"},{"key":"39_CR5","unstructured":"Assadi, S., Khanna, S., Li, Y., Yaroslavtsev, G.: Tight bounds for linear sketches of approximate matchings. CoRR, abs\/1505.01467 (2015)"},{"key":"39_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/978-3-319-13123-8_6","volume-title":"Algorithms and Models for the Web Graph","author":"B Bahmani","year":"2014","unstructured":"Bahmani, B., Goel, A., Munagala, K.: Efficient primal-dual graph algorithms for mapreduce. In: Bonato, A., Graham, F.C., Pra\u0142at, P. (eds.) WAW 2014. LNCS, vol. 8882, pp. 59\u201378. Springer, Heidelberg (2014)"},{"issue":"5","key":"39_CR7","first-page":"454","volume":"5","author":"B Bahmani","year":"2012","unstructured":"Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and mapreduce. PVLDB 5(5), 454\u2013465 (2012)","journal-title":"PVLDB"},{"key":"39_CR8","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: STOC (2015)","DOI":"10.1145\/2746539.2746592"},{"key":"39_CR9","doi-asserted-by":"crossref","unstructured":"Bury, M., Schwiegelshohn, C.: Sublinear estimation of weighted matchings in dynamic data streams. CoRR, abs\/1505.02019 (2015)","DOI":"10.1007\/978-3-662-48350-3_23"},{"key":"39_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M Charikar","year":"2000","unstructured":"Charikar, M.: Greedy approximation algorithms for finding dense components in a graph. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 84\u201395. Springer, Heidelberg (2000)"},{"key":"39_CR11","unstructured":"Chitnis, R.H., Cormode, G., Esfandiari, H., Hajiaghayi, M., McGregor, A., Monemizadeh, M., Vorotnikova, S.: Kernelization via sampling with applications to dynamic graph streams. CoRR, abs\/1505.01731 (2015)"},{"issue":"3","key":"39_CR12","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10619-013-7131-9","volume":"32","author":"G Cormode","year":"2014","unstructured":"Cormode, G., Firmani, D.: A unifying framework for $$\\ell _0$$ -sampling algorithms. Distrib. Parallel Databases 32(3), 315\u2013335 (2014)","journal-title":"Distrib. Parallel Databases"},{"issue":"1","key":"39_CR13","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"39_CR14","doi-asserted-by":"crossref","unstructured":"Epasto, A., Lattanzi, S., Sozio, M.: Efficient densest subgraph computation in evolving graphs. In: WWW (2015)","DOI":"10.1145\/2736277.2741638"},{"issue":"1","key":"39_CR15","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Comput. 18(1), 30\u201355 (1989)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"39_CR16","doi-asserted-by":"publisher","first-page":"937","DOI":"10.1109\/JPROC.2010.2045092","volume":"98","author":"AC Gilbert","year":"2010","unstructured":"Gilbert, A.C., Indyk, P.: Sparse recovery using sparse matrices. Proc. IEEE 98(6), 937\u2013947 (2010)","journal-title":"Proc. IEEE"},{"key":"39_CR17","unstructured":"Goel, A., Kapralov, M., Post, I.: Single pass sparsification in the streaming model with edge deletions. CoRR, abs\/1203.4900 (2012)"},{"key":"39_CR18","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, Berkeley, CA, USA (1984)"},{"key":"39_CR19","doi-asserted-by":"crossref","unstructured":"Guha, S., McGregor, A., Tench, D.: Vertex and hypergraph connectivity in dynamic graph streams. In: PODS (2015)","DOI":"10.1145\/2745754.2745763"},{"key":"39_CR20","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Saglam, M., Tardos, G.: Tight bounds for lp samplers, finding duplicates in streams, and related problems. In: PODS, pp. 49\u201358 (2011)","DOI":"10.1145\/1989284.1989289"},{"key":"39_CR21","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Lee, Y.T., Musco, C., Musco, C., Sidford, A.: Single pass spectral sparsification in dynamic streams. In: FOCS (2014)","DOI":"10.1109\/FOCS.2014.66"},{"key":"39_CR22","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Woodruff, D.P.: Spanners and sparsifiers in dynamic streams. In: ACM Symposium on Principles of Distributed Computing, PODC 2014, Paris, France, July 15\u201318, 2014, pp. 272\u2013281 (2014)","DOI":"10.1145\/2611462.2611497"},{"key":"39_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1007\/978-3-642-02927-1_50","volume-title":"Automata, Languages and Programming","author":"S Khuller","year":"2009","unstructured":"Khuller, S., Saha, B.: On finding dense subgraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 597\u2013608. Springer, Heidelberg (2009)"},{"key":"39_CR24","doi-asserted-by":"crossref","unstructured":"Konrad, C.: Maximum matching in turnstile streams. CoRR, abs\/1505.01460 (2015)","DOI":"10.1007\/978-3-662-48350-3_70"},{"key":"39_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1007\/978-3-319-08404-6_27","volume-title":"Algorithm Theory \u2013 SWAT 2014","author":"K Kutzkov","year":"2014","unstructured":"Kutzkov, K., Pagh, R.: Triangle counting in dynamic graph streams. In: Ravi, R., G\u00f8rtz, I.L. (eds.) SWAT 2014. LNCS, vol. 8503, pp. 306\u2013318. Springer, Heidelberg (2014)"},{"key":"39_CR26","series-title":"Advances in Database Systems","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-1-4419-6045-0_10","volume-title":"Managing and Mining Graph Data","author":"V Lee","year":"2010","unstructured":"Lee, V., Ruan, N., Jin, R., Aggarwal, C.: A survey of algorithms for dense subgraph discovery. In: Aggarwal, C.C., Wang, H. (eds.) Managing and Mining Graph Data. Advances in Database Systems, vol. 40, pp. 303\u2013336. Springer, US (2010)"},{"issue":"1","key":"39_CR27","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. SIGMOD Rec. 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Rec."},{"key":"39_CR28","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603","volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"M Mitzenmacher","year":"2005","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York (2005)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T01:55:45Z","timestamp":1567043745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}