{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:42Z","timestamp":1781077782138,"version":"3.54.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319961507","type":"print"},{"value":"9783319961514","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-96151-4_9","type":"book-chapter","created":{"date-parts":[[2018,7,17]],"date-time":"2018-07-17T12:21:49Z","timestamp":1531830109000},"page":"101-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximating the Caro-Wei Bound for Independent Sets in Graph Streams"],"prefix":"10.1007","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacques","family":"Dark","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christian","family":"Konrad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,7,18]]},"reference":[{"issue":"2","key":"9_CR1","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/s00453-015-0051-5","volume":"76","author":"BV Halld\u00f3rsson","year":"2016","unstructured":"Halld\u00f3rsson, B.V., Halld\u00f3rsson, M.M., Losievskaja, E., Szegedy, M.: Streaming algorithms for independent sets in sparse hypergraphs. Algorithmica 76(2), 490\u2013501 (2016)","journal-title":"Algorithmica"},{"key":"9_CR2","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations. IRSS, pp. 85\u2013103. Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. Acta Math. 182(1), 105\u2013142 (1999)","journal-title":"Acta Math."},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."},{"issue":"2","key":"9_CR5","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1137\/S089548010240415X","volume":"18","author":"U Feige","year":"2005","unstructured":"Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219\u2013225 (2005)","journal-title":"SIAM J. Discret. Math."},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. In: STOC, pp. 439\u2013448 (1994)","DOI":"10.1145\/195058.195221"},{"key":"9_CR7","unstructured":"Wei, V.: A lower bound on the stability number of a simple graph. Technical report, Bell Labs (1981)"},{"issue":"1","key":"9_CR8","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/0095-8956(83)90003-5","volume":"34","author":"JR Griggs","year":"1983","unstructured":"Griggs, J.R.: Lower bounds on the independence number in terms of the degrees. J. Comb. Theory Ser. B 34(1), 22\u201339 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"9_CR9","unstructured":"Caro, Y.: New results on the independence number. Technical report, Tel Aviv Univ (1979)"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/978-3-662-48653-5_37","volume-title":"Distributed Computing","author":"MM Halld\u00f3rsson","year":"2015","unstructured":"Halld\u00f3rsson, M.M., Konrad, C.: Distributed large independent sets in one round on bounded-independence graphs. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 559\u2013572. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48653-5_37"},{"key":"9_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-642-31594-7_38","volume-title":"Automata, Languages, and Programming","author":"MM Halld\u00f3rsson","year":"2012","unstructured":"Halld\u00f3rsson, M.M., Sun, X., Szegedy, M., Wang, C.: Streaming and communication complexity of clique approximation. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 449\u2013460. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_38"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Assadi, S., Khanna, S., Li, Y.: On estimating maximum matching size in graph streams. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1723\u20131742 (2017)","DOI":"10.1137\/1.9781611974782.113"},{"key":"9_CR13","unstructured":"Cormode, G., Jowhari, H., Monemizadeh, M., Muthukrishnan, S.: The sparse awakens: streaming algorithms for matching size estimation in sparse graphs. In: ESA (2017)"},{"key":"9_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-319-21840-3_11","volume-title":"Algorithms and Data Structures","author":"S Cabello","year":"2015","unstructured":"Cabello, S., P\u00e9rez-Lantero, P.: Interval selection in the streaming model. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 127\u2013139. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21840-3_11"},{"issue":"1","key":"9_CR15","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. 58(1), 137\u2013147 (1999)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1007\/978-0-387-39940-9","volume-title":"Encyclopedia of Database Systems","author":"DP Woodruff","year":"2009","unstructured":"Woodruff, D.P.: Frequency moments. In: Liu, L., \u00d6zsu, M.T. (eds.) Encyclopedia of Database Systems, pp. 1169\u20131170. Springer, Boston (2009). https:\/\/doi.org\/10.1007\/978-0-387-39940-9"},{"key":"9_CR17","unstructured":"Braverman, V., Chestnut, S.R.: Universal sketches for the frequency negative moments and other decreasing streaming sums. In: APPROX\/RANDOM, pp. 591\u2013605 (2015)"},{"issue":"436\u2013452","key":"9_CR18","first-page":"137","volume":"48","author":"P Tur\u00e1n","year":"1941","unstructured":"Tur\u00e1n, P.: On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok 48(436\u2013452), 137 (1941)","journal-title":"Matematikai \u00e9s Fizikai Lapok"},{"key":"9_CR19","unstructured":"Henzinger, M., Raghavan, P., Rajagopalan, S.: Computing on data streams. Technical report SRC 1998\u2013011, DEC Systems Research Centre (1998)"},{"issue":"1","key":"9_CR20","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1145\/2627692.2627694","volume":"43","author":"A McGregor","year":"2014","unstructured":"McGregor, A.: Graph stream algorithms: a survey. SIGMOD Rec. 43(1), 9\u201320 (2014)","journal-title":"SIGMOD Rec."},{"issue":"3","key":"9_CR21","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1137\/100783066","volume":"25","author":"M Gonen","year":"2011","unstructured":"Gonen, M., Ron, D., Shavitt, Y.: Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math. 25(3), 1365\u20131411 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"9_CR22","unstructured":"Eden, T., Ron, D., Seshadhri, C.: Sublinear time estimation of degree distribution moments: the arboricity connection. CoRR abs\/1604.03661 (2016)"},{"key":"9_CR23","unstructured":"Aliakbarpour, M., Biswas, A.S., Gouleakis, T., Peebles, J., Rubinfeld, R., Yodpinyanee, A.: Sublinear-time algorithms for counting star subgraphs with applications to join selectivity estimation. CoRR abs\/1601.04233 (2016)"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Sa\u011flam, M., Tardos, G.: Tight bounds for Lp samplers, finding duplicates in streams, and related problems. In: ACM Principles of Database Systems (2011)","DOI":"10.1145\/1989284.1989289"},{"issue":"4","key":"9_CR25","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545\u2013557 (1992)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-96151-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,20]],"date-time":"2019-10-20T19:04:29Z","timestamp":1571598269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-96151-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319961507","9783319961514"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-96151-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"ISCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marrakesh","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Morocco","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"isco2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/isco2018.lip6.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}