{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:40:01Z","timestamp":1748562001541,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662480533"},{"type":"electronic","value":"9783662480540"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-662-48054-0_13","type":"book-chapter","created":{"date-parts":[[2015,8,10]],"date-time":"2015-08-10T11:57:29Z","timestamp":1439207849000},"page":"151-162","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory"],"prefix":"10.1007","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zaoxing","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tejasvam","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lin F.","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/978-3-642-02930-1_27","volume-title":"Automata, Languages and Programming","author":"KJ 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. 5556, pp. 328\u2013338. Springer, Heidelberg (2009)"},{"key":"13_CR2","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 594\u2013598. ACM\/SIAM (1998). http:\/\/dl.acm.org\/citation.cfm?id=314613.315014"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing. pp. 20\u201329. ACM (1996)","DOI":"10.1145\/237814.237823"},{"key":"13_CR4","unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 623\u2013632. SODA, Society for Industrial and Applied Mathematics (2002)"},{"key":"13_CR5","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Computing clustering coefficients in data streams. In: European Conference on Complex Systems (ECCS) (2006)"},{"key":"13_CR6","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Proceedings of the Twenty-fifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pp. 253\u2013262. ACM (2006)","DOI":"10.1145\/1142351.1142388"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1007\/978-3-540-75520-3_55","volume-title":"Algorithms \u2013 ESA 2007","author":"LS Buriol","year":"2007","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Sohler, C.: Estimating clustering indexes in data streams. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 618\u2013632. Springer, Heidelberg (2007)"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Spaccamela, A.M., Sohler, C.: Counting graph minors in data streams. Technical report, DELIS - Dynamically Evolving, Large-Scale Information Systems (2005)","DOI":"10.1145\/1142351.1142388"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Khot, S., Sun, X.: Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In: IEEE Conference on Computational Complexity, pp. 107\u2013117. IEEE Computer Society (2003)","DOI":"10.1109\/CCC.2003.1214414"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0602001","volume":"2","author":"F Chung","year":"1981","unstructured":"Chung, F.: On the decomposition of graphs. SIAM J. Algebraic Discrete Methods 2(1), 1\u201312 (1981)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-0348-5438-2_10","volume-title":"Studies in Pure Mathematics","author":"F Chung","year":"1983","unstructured":"Chung, F., Erd\u0151s, P., Spencer, J.: On the decomposition of graphs into complete bipartite subgraphs. In: Erd\u0151s, P., Alp\u00e1r, L., Hal\u00e1sz, H., S\u00e1rk\u00d6z, A. (eds.) Studies in Pure Mathematics, pp. 95\u2013101. Birkh\u00e4user, Basel (1983)"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2014.07.025","volume":"552","author":"G Cormode","year":"2014","unstructured":"Cormode, G., Jowhari, H.: A second look at counting triangles in graph streams. Theoret. Comput. Sci. 552, 44\u201351 (2014)","journal-title":"Theoret. Comput. Sci."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Finocchi, I., Ribichini, A.: Trading off space for passes in graph streaming problems. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms. pp. 714\u2013723. ACM (2006)","DOI":"10.1145\/1109557.1109635"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1109\/TIT.2006.871582","volume":"52","author":"DL Donoho","year":"2006","unstructured":"Donoho, D.L.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289\u20131306 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Goel, A., Kapralov, M., Khanna, S.: On the communication and streaming complexity of maximum bipartite matching. In: Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 468\u2013485. SIAM (2012)","DOI":"10.1137\/1.9781611973099.41"},{"key":"13_CR16","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, Part I. LNCS, vol. 7391, pp. 449\u2013460. Springer, Heidelberg (2012)"},{"key":"13_CR17","unstructured":"Jha, M., Seshadhri, C., Pinar, A.: When a graph is not so simple: Counting triangles in multigraph streams. CoRR abs\/1310.7665 (2013). http:\/\/arxiv.org\/abs\/1310.7665"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1007\/11533719_72","volume-title":"Computing and Combinatorics","author":"H Jowhari","year":"2005","unstructured":"Jowhari, H., Ghodsi, M.: New Streaming algorithms for counting triangles in graphs. In: Wang, L. (ed.) COCOON 2005. LNCS, vol. 3595, pp. 710\u2013716. Springer, Heidelberg (2005)"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Streaming lower bounds for approximating MAX-CUT. CoRR abs\/1409.2138 (2014). http:\/\/arxiv.org\/abs\/1409.2138","DOI":"10.1137\/1.9781611973730.84"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Kutzkov, K., Pagh, R.: On the streaming complexity of computing local clustering coefficients. In: Proceedings of the Sixth ACM International Conference on Web Search and Data Mining (WSDM), pp. 677\u2013686. ACM (2013)","DOI":"10.1145\/2433396.2433480"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1007\/978-3-642-23719-5_57","volume-title":"Algorithms \u2013 ESA 2011","author":"M Manjunath","year":"2011","unstructured":"Manjunath, M., Mehlhorn, K., Panagiotou, K., Sun, H.: Approximate counting of cycles in streams. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 677\u2013688. Springer, Heidelberg (2011)"},{"issue":"1","key":"13_CR22","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). http:\/\/doi.acm.org\/10.1145\/2627692.2627694","journal-title":"SIGMOD Rec."},{"issue":"14","key":"13_CR23","doi-asserted-by":"publisher","first-page":"1870","DOI":"10.14778\/2556549.2556569","volume":"6","author":"A Pavan","year":"2013","unstructured":"Pavan, A., Tangwongsan, K., Tirthapura, S., Wu, K.L.: Counting and sampling triangles from a graph stream. Proc. VLDB Endowment 6(14), 1870\u20131881 (2013)","journal-title":"Proc. VLDB Endowment"},{"key":"13_CR24","unstructured":"Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the facebook social graph. CoRR abs\/1111.4503 (2011). http:\/\/arxiv.org\/abs\/1111.4503"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2015"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48054-0_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T23:08:08Z","timestamp":1748560088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-48054-0_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662480533","9783662480540"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48054-0_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"11 August 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}