{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,25]],"date-time":"2025-10-25T14:14:10Z","timestamp":1761401650993},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642403279"},{"type":"electronic","value":"9783642403286"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40328-6_1","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T09:17:34Z","timestamp":1376644654000},"page":"1-10","source":"Crossref","is-referenced-by-count":23,"title":["Spectral Sparsification in Dynamic Graph Streams"],"prefix":"10.1007","author":[{"given":"Kook Jin","family":"Ahn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D. Achlioptas","year":"2003","unstructured":"Achlioptas, D.: Database-friendly random projections: Johnson-lindenstrauss with binary coins. J. Comput. Syst. Sci.\u00a066(4), 671\u2013687 (2003)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Analyzing graph structure via linear measurements. In: SODA, pp. 459\u2013467 (2012)","key":"1_CR2","DOI":"10.1137\/1.9781611973099.40"},{"doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: PODS, pp. 5\u201314 (2012)","key":"1_CR3","DOI":"10.1145\/2213556.2213560"},{"doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t minimum cuts in \u00f5(n\n                  2) time. In: STOC, pp. 47\u201355 (1996)","key":"1_CR4","DOI":"10.1145\/237814.237827"},{"issue":"2","key":"1_CR5","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1109\/TIT.2005.862083","volume":"52","author":"E.J. Cand\u00e8s","year":"2006","unstructured":"Cand\u00e8s, E.J., Romberg, J.K., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory\u00a052(2), 489\u2013509 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"doi-asserted-by":"crossref","unstructured":"Christiano, P., Kelner, J.A., Madry, A., Spielman, D.A., Teng, S.-H.: Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In: STOC, pp. 273\u2013282 (2011)","key":"1_CR6","DOI":"10.1145\/1993636.1993674"},{"doi-asserted-by":"crossref","unstructured":"Cormode, G.: Sketch techniques for approximate query processing. In: Cormode, G., Garofalakis, M., Haas, P., Jermaine, C. (eds.) Synposes for Approximate Query Processing: Samples, Histograms, Wavelets and Sketches. Foundations and Trends in Databases. NOW Publishers (2011)","key":"1_CR7","DOI":"10.1561\/1900000004"},{"issue":"4","key":"1_CR8","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"D.L. Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Transactions on Information Theory\u00a052(4), 1289\u20131306 (2006)","journal-title":"IEEE Transactions on Information Theory"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/3-540-36478-1_4","volume-title":"Combinatorial Optimization - Eureka, You Shrink!","author":"J. Edmonds","year":"2003","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization (Edmonds Festschrift). LNCS, vol.\u00a02570, pp. 31\u201333. Springer, Heidelberg (2003)"},{"issue":"2-3","key":"1_CR10","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-3), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"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)","key":"1_CR11","DOI":"10.1145\/1993636.1993647"},{"key":"1_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipshitz mapping into Hilbert Space. Contemporary Mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary Mathematics"},{"doi-asserted-by":"crossref","unstructured":"Kane, D.M., Nelson, J., Woodruff, D.P.: An optimal algorithm for the distinct elements problem. In: PODS, pp. 41\u201352 (2010)","key":"1_CR13","DOI":"10.1145\/1807085.1807094"},{"unstructured":"Karzanov, A.: Determining a maximal flow in a network by the method of preflows. Soviet Math. Dokl.\u00a015(2) (1974)","key":"1_CR14"},{"unstructured":"Kelner, J.A., Levin, A.: Spectral sparsification in the semi-streaming setting. In: STACS, pp. 440\u2013451 (2011)","key":"1_CR15"},{"doi-asserted-by":"crossref","unstructured":"Khandekar, R., Rao, S., Vazirani, U.V.: Graph partitioning using single commodity flows. J. ACM\u00a056(4) (2009)","key":"1_CR16","DOI":"10.1145\/1538902.1538903"},{"issue":"1","key":"1_CR17","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1006\/jcta.1998.2930","volume":"86","author":"R. Lyons","year":"1999","unstructured":"Lyons, R., Pemantle, R., Peres, Y.: Resistance bounds for first-passage percolation and maximum flow. J. Comb. Theory, Ser. A\u00a086(1), 158\u2013168 (1999)","journal-title":"J. Comb. Theory, Ser. A"},{"issue":"4","key":"1_CR18","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/BF01305237","volume":"12","author":"N. Nisan","year":"1992","unstructured":"Nisan, N.: Pseudorandom generators for space-bounded computation. Combinatorica\u00a012(4), 449\u2013461 (1992)","journal-title":"Combinatorica"},{"issue":"6","key":"1_CR19","doi-asserted-by":"publisher","first-page":"1913","DOI":"10.1137\/080734029","volume":"40","author":"D.A. Spielman","year":"2011","unstructured":"Spielman, D.A., Srivastava, N.: Graph sparsification by effective resistances. SIAM J. Comput.\u00a040(6), 1913\u20131926 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: STOC, pp. 81\u201390 (2004)","key":"1_CR20","DOI":"10.1145\/1007352.1007372"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40328-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T13:42:00Z","timestamp":1558014120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40328-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642403279","9783642403286"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40328-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}