{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T01:21:48Z","timestamp":1773796908385,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,8,19]],"date-time":"2015-08-19T00:00:00Z","timestamp":1439942400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Icelandic Research Fund","award":["7000921"],"award-info":[{"award-number":["7000921"]}]},{"name":"Icelandic Research Fund","award":["90032021"],"award-info":[{"award-number":["90032021"]}]},{"name":"Icelandic Research Fund","award":["12003211"],"award-info":[{"award-number":["12003211"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s00453-015-0051-5","type":"journal-article","created":{"date-parts":[[2015,8,18]],"date-time":"2015-08-18T09:20:53Z","timestamp":1439889653000},"page":"490-501","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Streaming Algorithms for Independent Sets in Sparse Hypergraphs"],"prefix":"10.1007","volume":"76","author":[{"given":"Bjarni V.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elena","family":"Losievskaja","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mario","family":"Szegedy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,19]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S.: Graph sparsification in the semi-streaming model. In: Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, 5\u201312 July 2009, Proceedings, pp. 328\u2013338 (2009)","DOI":"10.1007\/978-3-642-02930-1_27"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Arad, U., Azar, Y.: Independent sets in hypergraphs with applications to routing via fixed paths. In: Proceedings of Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX\u201999, pp. 16\u201327 (1999)","DOI":"10.1007\/978-3-540-48413-4_3"},{"key":"51_CR3","volume-title":"The Probabilistic Method","author":"N Alon","year":"1992","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992)"},{"key":"51_CR4","unstructured":"Caro, Y.: New Results on the Independence Number. Technical report, Tel-Aviv University (1979)"},{"issue":"1","key":"51_CR5","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1002\/jgt.3190150110","volume":"15","author":"Y Caro","year":"1991","unstructured":"Caro, Y., Tuza, Z.: Improved lower bounds on k-independence. J. Graph Theory 15(1), 99\u2013107 (1991)","journal-title":"J. Graph Theory"},{"issue":"2","key":"51_CR6","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/s00453-011-9598-y","volume":"65","author":"G Cormode","year":"2013","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Streaming graph computations with a helpful advisor. Algorithmica 65(2), 409\u2013442 (2013)","journal-title":"Algorithmica"},{"issue":"4","key":"51_CR7","doi-asserted-by":"crossref","first-page":"728","DOI":"10.1137\/110820774","volume":"41","author":"Y Emek","year":"2012","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Mansour, Y., Patt-Shamir, B., Radhakrishnan, J., Rawitz, D.: Online set packing. SIAM J. Comput. 41(4), 728\u2013746 (2012)","journal-title":"SIAM J. Comput."},{"key":"51_CR8","doi-asserted-by":"crossref","unstructured":"Emek, Y., Halld\u00f3rsson, M.M., Ros\u00e9n, A.: Space-constrained interval selection. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick, UK, 9\u201313 July 2012, Proceedings, Part I, pp. 302\u2013313 (2012)","DOI":"10.1007\/978-3-642-31594-7_26"},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"Emek, Y., Ros\u00e9n, A.: Semi-streaming set cover - (extended abstract). In: Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, 8\u201311 July 2014, Proceedings, Part I, pp. 453\u2013464 (2014)","DOI":"10.1007\/978-3-662-43948-7_38"},{"issue":"3","key":"51_CR10","doi-asserted-by":"crossref","first-page":"1251","DOI":"10.1137\/100801901","volume":"25","author":"L Epstein","year":"2011","unstructured":"Epstein, L., Levin, A., Mestre, J., Segev, D.: Improved approximation guarantees for weighted matching in the semi-streaming model. SIAM J. Discrete Math. 25(3), 1251\u20131265 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"51_CR11","doi-asserted-by":"crossref","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. 348(2), 207\u2013216 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"51_CR12","doi-asserted-by":"crossref","first-page":"1709","DOI":"10.1137\/070683155","volume":"38","author":"J Feigenbaum","year":"2008","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the data-stream model. SIAM J. Comput. 38(5), 1709\u20131727 (2008)","journal-title":"SIAM J. Comput."},{"key":"51_CR13","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets. In: Automata, Languages and Programming\u201437th International Colloquium, ICALP, Bordeaux, France, Proceedings, pp. 641\u2013652. Springer (2010)","DOI":"10.1007\/978-3-642-14165-2_54"},{"issue":"2","key":"51_CR14","doi-asserted-by":"crossref","first-page":"953","DOI":"10.1016\/S0304-3975(01)00411-X","volume":"289","author":"MM Halld\u00f3rsson","year":"2002","unstructured":"Halld\u00f3rsson, M.M., Iwama, K., Miyazaki, S., Taketomi, S.: Online independent sets. Theor. Comput. Sci. 289(2), 953\u2013962 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"51_CR15","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Sun, X., Szegedy, M., Wang, C.: Streaming and communication complexity of clique approximation. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick, UK, 9\u201313 July 2012, Proceedings, Part I, pp. 449\u2013460 (2012)","DOI":"10.1007\/978-3-642-31594-7_38"},{"issue":"2","key":"51_CR16","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1561\/0400000002","volume":"1","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S.: Data streams: algorithms and applications. Found. Trends Theor. Comput. Sci. 1(2), 117\u2013236 (2005)","journal-title":"Found. Trends Theor. Comput. Sci."},{"issue":"3","key":"51_CR17","doi-asserted-by":"crossref","first-page":"488","DOI":"10.1137\/S0895480102419731","volume":"18","author":"H Shachnai","year":"2004","unstructured":"Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18(3), 488\u2013500 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"51_CR18","first-page":"436","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory (in Hungarian). Mat. Fiz. Lapok 48, 436\u2013452 (1941)","journal-title":"Mat. Fiz. Lapok"},{"key":"51_CR19","unstructured":"Wei, V.K.: A lower bound on the stability number of a simple graph. Technical Memorandum No. 81-11217-9, Bell Laboratories (1981)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0051-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0051-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0051-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,29]],"date-time":"2019-08-29T10:18:49Z","timestamp":1567073929000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0051-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,19]]},"references-count":19,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["51"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0051-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,8,19]]}}}