{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T10:01:04Z","timestamp":1767866464724,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T00:00:00Z","timestamp":1576281600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["20174LF3T8"],"award-info":[{"award-number":["20174LF3T8"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00453-019-00656-8","type":"journal-article","created":{"date-parts":[[2019,12,14]],"date-time":"2019-12-14T12:05:02Z","timestamp":1576325102000},"page":"1547-1573","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0770-2235","authenticated-orcid":false,"given":"Alessio","family":"Conte","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[]},{"given":"Luca","family":"Versari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,12,14]]},"reference":[{"key":"656_CR1","doi-asserted-by":"crossref","unstructured":"Ahmed, N.K., Neville, J., Rossi, R.A., Duffield, N.G.: Efficient graphlet counting for large networks. In: 2015 IEEE International Conference on Data Mining, ICDM 2015, pp. 1\u201310. IEEE (2015)","DOI":"10.1109\/ICDM.2015.141"},{"issue":"1","key":"656_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0202001","volume":"2","author":"EA Akkoyunlu","year":"1973","unstructured":"Akkoyunlu, E.A.: The enumeration of maximal cliques of large graphs. SIAM J. Comput. 2(1), 1\u20136 (1973)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"656_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"issue":"1\u20133","key":"656_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1\u20133), 21\u201346 (1996)","journal-title":"Discrete Appl. Math."},{"key":"656_CR5","unstructured":"Bierstone, E.: Cliques and generalized cliques in a finite linear graph. Unpublished report (1960)"},{"key":"656_CR6","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Pagh, R., Williams, V.V., Zwick, U.: Listing triangles. In: Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Proceedings, Part I, pp. 223\u2013234 (2014)","DOI":"10.1007\/978-3-662-43948-7_19"},{"issue":"9","key":"656_CR7","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575\u2013576 (1973)","journal-title":"Commun. ACM"},{"issue":"1\u20133","key":"656_CR8","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1016\/j.tcs.2008.05.010","volume":"407","author":"F Cazals","year":"2008","unstructured":"Cazals, F., Karande, C.: A note on the problem of reporting maximal cliques. Theor. Comput. Sci. 407(1\u20133), 564\u2013568 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"656_CR9","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00453-012-9632-8","volume":"66","author":"L Chang","year":"2013","unstructured":"Chang, L., Yu, J.X., Qin, L.: Fast maximal cliques enumeration in sparse graphs. Algorithmica 66(1), 173\u2013186 (2013)","journal-title":"Algorithmica"},{"key":"656_CR10","doi-asserted-by":"crossref","unstructured":"Cheng, J., Zhu, L., Ke, Y., Chu, S.: Fast algorithms for maximal clique enumeration with limited memory. In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD, pp. 1240\u20131248 (2012)","DOI":"10.1145\/2339530.2339724"},{"issue":"1","key":"656_CR11","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"656_CR12","doi-asserted-by":"publisher","first-page":"1147","DOI":"10.1016\/j.jcss.2008.04.003","volume":"74","author":"S Cohen","year":"2008","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. J. Comput. Syst. Sci. 74(7), 1147\u20131159 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"656_CR13","unstructured":"Comin, C., Rizzi, R.: An improved upper bound on maximal clique listing via rectangular fast matrix multiplication. CoRR (2015). arXiv:1506.01082"},{"key":"656_CR14","unstructured":"Conte, A., Grossi, R., Marino, A., Versari, L.: Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Proceedings, July 11\u201315, 2016, Rome, Italy, p. 148 (2016)"},{"key":"656_CR15","unstructured":"Conte, A., De\u00a0Virgilio, R., Maccioni, A., Patrignani, M., Torlone, R.: Finding all maximal cliques in very large social networks. In: Proceedings of the 19th International Conference on Extending Database Technology, EDBT 2016, pp. 173\u2013184 (2016)"},{"key":"656_CR16","doi-asserted-by":"crossref","unstructured":"Conte, A., Grossi, R., Marino, A., Uno, T., Versari, L.: Listing maximal independent sets with minimal space and bounded delay. In: Fici, G., Sciortino, M., Venturini, R. (eds.) String Processing and Information Retrieval, pp. 144\u2013160. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-67428-5_13"},{"issue":"2","key":"656_CR17","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1137\/17M1152206","volume":"33","author":"A Conte","year":"2019","unstructured":"Conte, A., Grossi, R., Marino, A., Versari, L.: Listing maximal subgraphs satisfying strongly accessible properties. SIAM J. Discrete Math. 33(2), 587\u2013613 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"656_CR18","first-page":"403","volume":"1","author":"D Eppstein","year":"2010","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. ISAAC 1, 403\u2013414 (2010)","journal-title":"ISAAC"},{"key":"656_CR19","doi-asserted-by":"publisher","DOI":"10.1145\/2543629","author":"D Eppstein","year":"2013","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics. (2013). https:\/\/doi.org\/10.1145\/2543629","journal-title":"ACM J. Exp. Algorithmics."},{"key":"656_CR20","unstructured":"Fukuda, K.: Note on new complexity classes ENP, EP and CEP. https:\/\/www.inf.ethz.ch\/personal\/fukudak\/old\/ENP_home\/ENP_note.html (1996). Accessed 17 Feb 2016"},{"issue":"1","key":"656_CR21","first-page":"05","volume":"8","author":"EN Gilbert","year":"1956","unstructured":"Gilbert, E.N.: Enumeration of labelled graphs. Can. J. Math 8(1), 05\u2013411 (1956)","journal-title":"Can. J. Math"},{"issue":"7","key":"656_CR22","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1016\/j.dam.2008.10.010","volume":"157","author":"A G\u00e9ly","year":"2009","unstructured":"G\u00e9ly, A., Nourine, L., Sadi, B.: Enumeration aspects of maximal cliques and bicliques. Discrete Appl. Math. 157(7), 1447\u20131459 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"656_CR23","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"656_CR24","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-540-27810-8_23","volume-title":"Algorithm theory-SWAT 2004, Proceedings","author":"K Makino","year":"2004","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Hagerup, T., Katajainen, J. (eds.) Algorithm theory-SWAT 2004, Proceedings, pp. 260\u2013272. Springer, Berlin, Heidelberg (2004)"},{"key":"656_CR25","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298, 824\u2013827 (2002)","journal-title":"Science"},{"issue":"1","key":"656_CR26","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3(1), 23\u201328 (1965)","journal-title":"Israel J. Math."},{"issue":"2","key":"656_CR27","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1145\/321694.321698","volume":"19","author":"GD Mulligan","year":"1972","unstructured":"Mulligan, G.D., Corneil, D.G.: Corrections to Bierstone\u2019s algorithm for generating cliques. J. ACM 19(2), 244\u2013247 (1972)","journal-title":"J. ACM"},{"key":"656_CR28","unstructured":"Ruskey, F.: Combinatorial generation. Preliminary working draft, vol. 11, p. 20. University of Victoria, Victoria, BC, Canada (2003)"},{"issue":"4","key":"656_CR29","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jpdc.2009.01.003","volume":"69","author":"MC Schmidt","year":"2009","unstructured":"Schmidt, M.C., Samatova, N.F., Thomas, K., Park, B.-H.: A scalable, parallel algorithm for maximal clique enumeration. J. Parallel Distrib. Comput. 69(4), 417\u2013428 (2009)","journal-title":"J. Parallel Distrib. Comput."},{"key":"656_CR30","unstructured":"Shervashidze, N., Vishwanathan, S.V.N., Petri, T., Mehlhorn, K., Borgwardt, K.M.: Efficient graphlet kernels for large graph comparison. In: Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, AISTATS 2009, Volume\u00a05 of JMLR Proceedings, pp. 488\u2013495 (2009)"},{"issue":"1","key":"656_CR31","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"E Tomita","year":"2006","unstructured":"Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1), 28\u201342 (2006)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"656_CR32","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1073\/pnas.40.10.1004","volume":"40","author":"HM Trent","year":"1954","unstructured":"Trent, H.M.: A note on the enumeration and listing of all possible trees in a connected linear graph. Proc. Natl. Acad. Sci. 40(10), 1004\u20131007 (1954)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"1","key":"656_CR33","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1038\/scientificamerican0707-52","volume":"297","author":"JZ Tsien","year":"2007","unstructured":"Tsien, J.Z.: The memory code. Sci. Am. 297(1), 52\u201359 (2007)","journal-title":"Sci. Am."},{"issue":"3","key":"656_CR34","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"656_CR35","first-page":"2003","volume":"4","author":"T Uno","year":"2003","unstructured":"Uno, T.: Two general methods to reduce delay and change of enumeration algorithms. Natl. Inst. Inform. (in Japan) Tech. Rep. E 4, 2003 (2003)","journal-title":"Natl. Inst. Inform. (in Japan) Tech. Rep. E"},{"issue":"1","key":"656_CR36","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00453-008-9238-3","volume":"56","author":"T Uno","year":"2008","unstructured":"Uno, T.: An efficient algorithm for solving pseudo clique enumeration problem. Algorithmica 56(1), 3\u201316 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"656_CR37","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8(2), 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"key":"656_CR38","doi-asserted-by":"crossref","unstructured":"Wasa, K., Arimura, H., Uno, T.: Efficient enumeration of induced subtrees in a $$k$$-degenerate graph. In: Ahn, H.-K., Shin, C.-S. (eds.) Algorithms and Computation: 25th International Symposium, ISAAC 2014, Proceedings, pp. 94\u2013102. Springer, Cham (2014)","DOI":"10.1007\/978-3-319-13075-0_8"},{"key":"656_CR39","doi-asserted-by":"crossref","unstructured":"Xu, Y., Cheng, J., Fu, A.W.-C., Bu, Y.: Distributed maximal clique computation. In: 2014 IEEE International Congress on Big Data (BigData Congress), pp. 160\u2013167. IEEE (2014)","DOI":"10.1109\/BigData.Congress.2014.31"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00656-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00656-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00656-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,13]],"date-time":"2020-12-13T00:07:31Z","timestamp":1607818051000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00656-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,14]]},"references-count":39,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["656"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00656-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,14]]},"assertion":[{"value":"29 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 November 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 December 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}