{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:49:01Z","timestamp":1755838141510,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642029295"},{"type":"electronic","value":"9783642029301"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"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":[[2009]]},"DOI":"10.1007\/978-3-642-02930-1_27","type":"book-chapter","created":{"date-parts":[[2009,7,2]],"date-time":"2009-07-02T15:05:04Z","timestamp":1246547104000},"page":"328-338","source":"Crossref","is-referenced-by-count":37,"title":["Graph Sparsification in the Semi-streaming Model"],"prefix":"10.1007","author":[{"given":"Kook Jin","family":"Ahn","sequence":"first","affiliation":[]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"27_CR1","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N. Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The Space Complexity of Approximating the Frequency Moments. J. Comput. Syst. Sci.\u00a058(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/237814.237827","volume-title":"STOC 1996: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing","author":"A.A. Bencz\u00far","year":"1996","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t minimum cuts in O(n2) time. In: STOC 1996: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 47\u201355. ACM, New York (1996)"},{"key":"27_CR3","unstructured":"Chekuri, C.S., Goldberg, A.V., Karger, D.R., Levine, M.S., Stein, C.: Experimental study of minimum cut algorithms. In: SODA 1997: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 324\u2013333. Society for Industrial and Applied Mathematics (1997)"},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H.: A measure of the asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics\u00a023, 493\u2013509 (1952)","journal-title":"Annals of Mathematical Statistics"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: SODA, pp. 714\u2013723 (2006)","DOI":"10.1145\/1109557.1109635"},{"issue":"2","key":"27_CR6","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.\u00a0348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"27_CR7","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"R.E. Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Indust. Appl. Math.\u00a09(4), 551\u2013570 (1961)","journal-title":"J. Soc. Indust. Appl. Math."},{"key":"27_CR8","unstructured":"Hao, J., Orlin, J.B.: A faster algorithm for finding the minimum cut in a graph. In: SODA 1992: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 165\u2013174. Society for Industrial and Applied Mathematics (1992)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams (1998)","DOI":"10.1090\/dimacs\/050\/05"},{"key":"27_CR10","unstructured":"Karger, D.R.: Global min-cuts in rnc, and other ramifications of a simple min-out algorithm. In: SODA 1993: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, Philadelphia, PA, USA, pp. 21\u201330. Society for Industrial and Applied Mathematics (1993)"},{"key":"27_CR11","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1145\/195058.195422","volume-title":"STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing","author":"D.R. Karger","year":"1994","unstructured":"Karger, D.R.: Random sampling in cut, flow, and network design problems. In: STOC 1994: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pp. 648\u2013657. ACM Press, New York (1994)"},{"issue":"1","key":"27_CR12","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. J. ACM\u00a047(1), 46\u201376 (2000)","journal-title":"J. ACM"},{"issue":"4","key":"27_CR13","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/234533.234534","volume":"43","author":"D.R. Karger","year":"1996","unstructured":"Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM\u00a043(4), 601\u2013640 (1996)","journal-title":"J. ACM"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"McGregor, A.: Finding Graph Matchings in Data Streams. In: Proc. of APPROX-RANDOM, pp. 170\u2013181 (2005)","DOI":"10.1007\/11538462_15"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and Applications. Now publishers (2006)","DOI":"10.1561\/9781933019604"},{"key":"27_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":"27_CR17","first-page":"563","volume-title":"STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing","author":"D.A. Spielman","year":"2008","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. In: STOC 2008: Proceedings of the 40th annual ACM symposium on Theory of computing, pp. 563\u2013568. ACM Press, New York (2008)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-02930-1_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T05:52:31Z","timestamp":1589953951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-02930-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642029295","9783642029301"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-02930-1_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}