{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:29Z","timestamp":1759638749775,"version":"3.41.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T00:00:00Z","timestamp":1484697600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T00:00:00Z","timestamp":1484697600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1447639"],"award-info":[{"award-number":["1447639"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects","doi-asserted-by":"publisher","award":["N660001-1-2-4014"],"award-info":[{"award-number":["N660001-1-2-4014"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422668"],"award-info":[{"award-number":["CCF-1422668"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-017-0277-5","type":"journal-article","created":{"date-parts":[[2017,1,18]],"date-time":"2017-01-18T16:15:48Z","timestamp":1484756148000},"page":"652-667","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","volume":"80","author":[{"given":"Vladimir","family":"Braverman","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9119-1679","authenticated-orcid":false,"given":"Zaoxing","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Tejasvam","family":"Singh","sequence":"additional","affiliation":[]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[]},{"given":"Lin F.","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,18]]},"reference":[{"key":"277_CR1","doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S.: Graph sparsification in the semi-streaming model. In: Proceedings of the 36th International Colloquium on Automata. Languages and Programming: Part II, pp. 328\u2013338. Springer, ICALP (2009)","DOI":"10.1007\/978-3-642-02930-1_27"},{"key":"277_CR2","doi-asserted-by":"crossref","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)","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.3.CO;2-K"},{"key":"277_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":"277_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":"277_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":"277_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, pp. 253\u2013262. PODS, ACM (2006)","DOI":"10.1145\/1142351.1142388"},{"key":"277_CR7","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Sohler, C.: Estimating clustering indexes in data streams. In: ESA. Lecture Notes in Computer Science, vol. 4698, pp. 618\u2013632. Springer (2007)","DOI":"10.1007\/978-3-540-75520-3_55"},{"key":"277_CR8","doi-asserted-by":"crossref","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Spaccamela, A.M., Sohler, C.: Counting graph minors in data streams. Tech. rep, DELIS\u2014Dynamically Evolving, Large-Scale Information Systems (2005)","DOI":"10.1145\/1142351.1142388"},{"key":"277_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":"277_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. Algebr. Discrete Methods 2(1), 1\u201312 (1981)","journal-title":"SIAM J. Algebr. Discrete Methods"},{"key":"277_CR11","doi-asserted-by":"crossref","unstructured":"Chung, F., Erd\u0151s, P., Spencer, J.: On the decomposition of graphs into complete bipartite subgraphs. In: Studies in Pure Mathematics, pp. 95\u2013101. Birkh\u00e4user Basel (1983)","DOI":"10.1007\/978-3-0348-5438-2_10"},{"key":"277_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. Theor. Comput. Sci. 552, 44\u201351 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"277_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":"277_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":"277_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, pp. 468\u2013485. SODA, SIAM (2012)","DOI":"10.1137\/1.9781611973099.41"},{"key":"277_CR16","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., Sun, X., Szegedy, M., Wang, C.: Streaming and communication complexity of clique approximation. In: ICALP Proceedings of the 39th International Colloquium Conference on Automata, Languages, and Programming, vol. Part I, pp. 449\u2013460. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_38"},{"key":"277_CR17","doi-asserted-by":"publisher","unstructured":"Italiano, G.F., Pighizzini, G., Sannella, D. (eds.): Mathematical Foundations of Computer Science 2015\u201440th International Symposium, MFCS 2015, Milan, Italy, August 24\u201328, 2015, Proceedings, Part II, Lecture Notes in Computer Science, vol. 9235. Springer (2015). doi: 10.1007\/978-3-662-48054-0","DOI":"10.1007\/978-3-662-48054-0"},{"key":"277_CR18","unstructured":"Jha, M., Seshadhri, C., Pinar, A.: When a graph is not so simple: counting triangles in multigraph streams. CoRR. arXiv:1310.7665"},{"key":"277_CR19","doi-asserted-by":"crossref","unstructured":"Jowhari, H., Ghodsi, M.: New streaming algorithms for counting triangles in graphs. In: COCOON. Lecture Notes in Computer Science, vol. 3595, pp. 710\u2013716. Springer (2005)","DOI":"10.1007\/11533719_72"},{"key":"277_CR20","unstructured":"Kapralov, M., Khanna, S., Sudan, M.: Streaming lower bounds for approximating MAX-CUT. CoRR (2014). arXiv:1409.2138"},{"key":"277_CR21","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, pp. 677\u2013686. WSDM, ACM (2013)","DOI":"10.1145\/2433396.2433480"},{"key":"277_CR22","doi-asserted-by":"crossref","unstructured":"Manjunath, M., Mehlhorn, K., Panagiotou, K., Sun, H.: Approximate counting of cycles in streams. In: Proceedings of the 19th European Conference on Algorithms, pp. 677\u2013688. ESA, Springer (2011)","DOI":"10.1007\/978-3-642-23719-5_57"},{"issue":"1","key":"277_CR23","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."},{"key":"277_CR24","doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 401\u2013411. PODS \u201916, ACM, New York (2016). doi: 10.1145\/2902251.2902283","DOI":"10.1145\/2902251.2902283"},{"issue":"14","key":"277_CR25","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 Endow. 6(14), 1870\u20131881 (2013)","journal-title":"Proc. VLDB Endow."},{"key":"277_CR26","unstructured":"Tur$$\\acute{a}$$n, P.: On an extremal problem in graph theory. Matematikai $$\\acute{e}$$ s Fizikai Lapok (1941)"},{"key":"277_CR27","unstructured":"Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the facebook social graph. CoRR. arXiv:1111.4503"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0277-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0277-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0277-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T16:13:37Z","timestamp":1749917617000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0277-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,18]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["277"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0277-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,1,18]]},"assertion":[{"value":"25 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 January 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 January 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}