{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:53:54Z","timestamp":1780073634671,"version":"3.54.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642041273","type":"print"},{"value":"9783642041280","type":"electronic"}],"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-04128-0_43","type":"book-chapter","created":{"date-parts":[[2009,9,14]],"date-time":"2009-09-14T18:16:36Z","timestamp":1252952196000},"page":"480-491","source":"Crossref","is-referenced-by-count":6,"title":["Sparse Cut Projections in Graph Streams"],"prefix":"10.1007","author":[{"given":"Atish","family":"Das Sarma","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sreenivas","family":"Gollapudi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rina","family":"Panigrahy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"43_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/978-3-642-02930-1_27","volume-title":"ICALP 2009. Part II","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)"},{"issue":"2","key":"43_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02579166","volume":"6","author":"N. Alon","year":"1986","unstructured":"Alon, N.: Eigenvalues and expanders. Combinatorica\u00a06(2), 83\u201396 (1986)","journal-title":"Combinatorica"},{"key":"43_CR3","doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F.R.K., Lang, K.J.: Local Graph Partitioning using PageRank Vectors. In: FOCS, pp. 475\u2013486 (2006)","DOI":"10.1109\/FOCS.2006.44"},{"key":"43_CR4","doi-asserted-by":"crossref","unstructured":"Arora, S., Rao, S., Vazirani, U.V.: Expander flows, geometric embeddings and graph partitioning. In: STOC, pp. 222\u2013231 (2004)","DOI":"10.1145\/1007352.1007355"},{"key":"43_CR5","doi-asserted-by":"crossref","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Approximating s-t Minimum Cuts in \u00d5(n $^{\\mbox{2}}$ ) Time. In: STOC, pp. 47\u201355 (1996)","DOI":"10.1145\/237814.237827"},{"issue":"2","key":"43_CR6","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/0022-0000(84)90071-0","volume":"28","author":"S.N. Bhatt","year":"1984","unstructured":"Bhatt, S.N., Leighton, F.T.: A Framework for Solving VLSI Graph Layout Problems. J. Comput. Syst. Sci.\u00a028(2), 300\u2013343 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"43_CR7","doi-asserted-by":"crossref","unstructured":"Boppana, R.: Eigenvalues and graph bisection: an average case analysis. In: 28th IEEE Symposium on Foundations of Computer Science, FOCS (1987)","DOI":"10.1109\/SFCS.1987.22"},{"key":"43_CR8","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J.T., Mahdian, M., Saberi, A.: Exploring the community structure of newsgroups. In: KDD, pp. 783\u2013787 (2004)","DOI":"10.1145\/1014052.1016914"},{"key":"43_CR9","unstructured":"Sarma, A.D., Gollapudi, S., Panigrahy, R.: Estimating PageRank on graph streams. In: PODS, pp. 69\u201378 (2008)"},{"key":"43_CR10","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading of space for passes in graph streaming problems. In: ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 714\u2013723 (2006)","DOI":"10.1145\/1109557.1109635"},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Ron, D.: Property Testing in Bounded Degree Graphs. In: STOC, pp. 406\u2013415 (1997)","DOI":"10.1145\/258533.258627"},{"key":"43_CR12","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. In: External Memory Algorithms. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a050, pp. 107\u2013118 (1999)","DOI":"10.1090\/dimacs\/050\/05"},{"issue":"1","key":"43_CR13","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"},{"key":"43_CR14","unstructured":"Kleinberg, J.M.: Authoritative sources in a hyperlinked environment. In: SODA, pp. 668\u2013677 (1998)"},{"issue":"2","key":"43_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1145\/382979.383041","volume":"19","author":"R. Lempel","year":"2001","unstructured":"Lempel, R., Moran, S.: Salsa: the stochastic approach for link-structure analysis. ACM Trans. Inf. Syst.\u00a019(2), 131\u2013160 (2001)","journal-title":"ACM Trans. Inf. Syst."},{"key":"43_CR16","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1145\/1242572.1242636","volume-title":"WWW 2007: Proceedings of the 16th international conference on World Wide Web","author":"J. Leskovec","year":"2007","unstructured":"Leskovec, J., Dumais, S., Horvitz, E.: Web projections: learning from contextual subgraphs of the web. In: WWW 2007: Proceedings of the 16th international conference on World Wide Web, pp. 471\u2013480. ACM, New York (2007)"},{"key":"43_CR17","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Faloutsos, C.: Sampling from large graphs. In: KDD, pp. 631\u2013636 (2006)","DOI":"10.1145\/1150402.1150479"},{"key":"43_CR18","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Simonovits, M.: The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume. In: FOCS, pp. 346\u2013354 (1990)","DOI":"10.1109\/FSCS.1990.89553"},{"issue":"4","key":"43_CR19","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L. Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L., Simonovits, M.: Random Walks in a Convex Body and an Improved Volume Algorithm. Random Struct. Algorithms\u00a04(4), 359\u2013412 (1993)","journal-title":"Random Struct. Algorithms"},{"key":"43_CR20","doi-asserted-by":"crossref","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC hardness for multiway cut, 0-extension, and metric labeling. In: STOC, pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"43_CR21","doi-asserted-by":"crossref","unstructured":"Sinclair, A., Jerrum, M.: Conductance and the mixing property of markov chains; the approximation of the permanent resolved. In: Proc. of the 20th annual ACM Symposium on Theory of computing, pp. 235\u2013244 (1988)","DOI":"10.1145\/62212.62234"},{"key":"43_CR22","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)","DOI":"10.1145\/1007352.1007372"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-04128-0_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T04:16:01Z","timestamp":1739333761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-04128-0_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642041273","9783642041280"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-04128-0_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}