{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T06:30:52Z","timestamp":1790922652386,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_46","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T22:53:21Z","timestamp":1284591201000},"page":"531-543","source":"Crossref","is-referenced-by-count":40,"title":["On Graph Problems in a Semi-streaming Model"],"prefix":"10.1007","author":[{"given":"Joan","family":"Feigenbaum","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"McGregor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siddharth","family":"Suri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jian","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"3","key":"46_CR1","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s00453-001-0088-5","volume":"32","author":"J. Abello","year":"2002","unstructured":"Abello, J., Buchsbaum, A.L., Westbrook, J.R.: A Functional Approach to External Graph Algorithms. Algorithmica\u00a032(3), 437\u2013458 (2002)","journal-title":"Algorithmica"},{"key":"46_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/3-540-52846-6_75","volume-title":"SWAT \u201990","author":"I. Alth\u00f6fer","year":"1990","unstructured":"Alth\u00f6fer, I., Das, G., Dobkin, D., Joseph, D.: Generating sparse spanners for weighted graphs. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol.\u00a0447, pp. 26\u201337. Springer, Heidelberg (1990)"},{"issue":"1","key":"46_CR3","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. Journal of Computer and System Sciences\u00a058(1), 137\u2013147 (1999)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1-3","key":"46_CR4","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/S0304-3975(02)00569-8","volume":"299","author":"A.L. Buchsbaum","year":"2003","unstructured":"Buchsbaum, A.L., Giancarlo, R., Westbrook, J.R.: On finding common neighborhoods in massive graphs. Theoretical Computer Science\u00a0299(1-3), 707\u2013718 (2003)","journal-title":"Theoretical Computer Science"},{"key":"46_CR5","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 623\u2013632 (2002)"},{"key":"46_CR6","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"Bollob\u00e1s, B.: Extremal Graph Theory. Academic Press, New York (1978)"},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539794261295","volume":"28","author":"E. Cohen","year":"1998","unstructured":"Cohen, E.: Fast algorithms for constructing t-spanners and paths with stretch t. SIAM J. on Computing\u00a028, 210\u2013236 (1998)","journal-title":"SIAM J. on Computing"},{"key":"46_CR8","unstructured":"Drineas, P., Kannan, R.: Pass Efficient Algorithm for approximating large matrices. In: Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, pp. 223\u2013232 (2003)"},{"key":"46_CR9","doi-asserted-by":"crossref","unstructured":"Eppstein, D., Galil, Z., Italiano, G.F.: Dynamic graph algorithms. CRC Handbook of Algorithms and Theory of Computation, ch. 8 (1999)","DOI":"10.1201\/9781420049503-c9"},{"issue":"1","key":"46_CR10","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/S0097539799361701","volume":"32","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Kannan, S., Strauss, M., Viswanathan, M.: An approximate L1 difference algorithm for massive data streams. SIAM Journal on Computing\u00a032(1), 131\u2013151 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"46_CR11","doi-asserted-by":"crossref","unstructured":"Flajolet, P., Martin, G.N.: Probabilistic counting. In: Proc. 24th IEEE Symposium on Foundation of Computer Science, pp. 76\u201382 (1983)","DOI":"10.1109\/SFCS.1983.46"},{"key":"46_CR12","doi-asserted-by":"crossref","unstructured":"Gilbert, A.C., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.: Fast, small-space algorithms for approximate histogram maintenance. In: Proc. 34th ACM Symposium on Theory of Computing, pp. 389\u2013398 (2002)","DOI":"10.1145\/509907.509966"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"Guha, S., Koudas, N., Shim, K.: Data-streams and histograms. In: Proc. 33th ACM Symposium on Theory of Computing, pp. 471\u2013475 (2001)","DOI":"10.1145\/380752.380841"},{"key":"46_CR14","unstructured":"Rauch Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. Technical Report 1998-001, DEC Systems Research Center (1998)"},{"key":"46_CR15","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings and data stream computation. In: Proc. 41th IEEE Symposium on Foundations of Computer Science, pp. 189\u2013197 (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"46_CR16","series-title":"Oxford Lecture Series in Math. and its Appl","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198501626.001.0001","volume-title":"Fast Parallel Algorithms for Graph Matching Problems","author":"M. Karpinski","year":"1998","unstructured":"Karpinski, M., Rytter, W.: Fast Parallel Algorithms for Graph Matching Problems. Oxford Lecture Series in Math. and its Appl. Oxford University Press, Oxford (1998)"},{"key":"46_CR17","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1990","unstructured":"Kalyanasundaram, B., Schnitger, G.: The Probabilistic Communication Complexity of Set Intersection. SIAM Journal on Discrete Math.\u00a05, 545\u2013557 (1990)","journal-title":"SIAM Journal on Discrete Math."},{"key":"46_CR18","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Extracting large-scale knowledge bases from the web. In: Proceedings of the 25th VLDB Conference, pp. 639\u2013650 (1999)"},{"key":"46_CR19","unstructured":"Muthukrishnan, S.: Data streams: Algorithms and applications (2003), Available at http:\/\/athos.rutgers.edu\/~muthu\/stream-1-1.ps"},{"key":"46_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. Tarjan","year":"1983","unstructured":"Tarjan, R.: Data Structures and Network Algorithms. SIAM, Philadelphia (1983)"},{"issue":"1-2","key":"46_CR21","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(00)00128-9","volume":"76","author":"R. Uehara","year":"2000","unstructured":"Uehara, R., Chen, Z.: Parallel approximation algorithms for maximum weighted matching in general graphs. Information Processing Letters\u00a076(1-2), 13\u201317 (2000)","journal-title":"Information Processing Letters"}],"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-540-27836-8_46.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,30]],"date-time":"2024-03-30T14:09:15Z","timestamp":1711807755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_46"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_46","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}