{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T04:35:37Z","timestamp":1784349337748,"version":"3.55.0"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T00:00:00Z","timestamp":1581724800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T00:00:00Z","timestamp":1581724800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2020,9]]},"DOI":"10.1007\/s00778-020-00602-z","type":"journal-article","created":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T03:02:24Z","timestamp":1581735744000},"page":"999-1022","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Efficient maximum clique computation and enumeration over large sparse graphs"],"prefix":"10.1007","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,2,15]]},"reference":[{"key":"602_CR1","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/j.tcs.2015.09.023","volume":"609","author":"T Akiba","year":"2016","unstructured":"Akiba, T., Iwata, Y.: Branch-and-reduce exponential\/fpt algorithms in practice: a case study of vertex cover. Theor. Comput. Sci. 609, 211\u2013225 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"602_CR2","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","volume":"18","author":"DV Andrade","year":"2012","unstructured":"Andrade, D.V., Resende, M.G.C., Werneck, R.F.: Fast local search for the maximum independent set problem. J. Heuristics 18(4), 525\u2013547 (2012)","journal-title":"J. Heuristics"},{"key":"602_CR3","unstructured":"Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. CoRR, cs.DS\/0310049 (2003)"},{"issue":"2","key":"602_CR4","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theor. Comput. Sys. 32(2), 115\u2013132 (1999)","journal-title":"Theor. Comput. Sys."},{"key":"602_CR5","unstructured":"Berry, N., Ko, T., Moy, T., Smrcka, J., Turnley, J., Ben, W.: Emergent clique formation in terrorist recruitmen. theory and practice. In: Workshop on Agent Organizations (2004)"},{"issue":"4\u20135","key":"602_CR6","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.physrep.2005.10.009","volume":"424","author":"S Boccaletti","year":"2006","unstructured":"Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D.-U.: Complex networks: structure and dynamics. Phys. Rep. 424(4\u20135), 175\u2013308 (2006)","journal-title":"Phys. Rep."},{"issue":"2","key":"602_CR7","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1016\/j.csda.2004.02.004","volume":"48","author":"V Boginski","year":"2005","unstructured":"Boginski, V., Butenko, S., Pardalos, P.M.: Statistical analysis of financial networks. Comput. Stat. Data Anal. 48(2), 431\u2013443 (2005)","journal-title":"Comput. Stat. Data Anal."},{"issue":"9","key":"602_CR8","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":"6","key":"602_CR9","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/0167-6377(90)90057-C","volume":"9","author":"R Carraghan","year":"1990","unstructured":"Carraghan, R., Pardalos, P.M.: An exact algorithm for the maximum clique problem. Oper. Res. Lett. 9(6), 375\u2013382 (1990)","journal-title":"Oper. Res. Lett."},{"key":"602_CR10","doi-asserted-by":"crossref","unstructured":"Chang, L.: Efficient maximum clique computation over large sparse graphs. In: Proceedings of SIGKDD\u201919 (2019)","DOI":"10.1145\/3292500.3330986"},{"key":"602_CR11","doi-asserted-by":"crossref","unstructured":"Chang, L., Li, W., Zhang, W.: Computing a near-maximum independent set in linear time by reducing-peeling. In: Proceedings of SIGMOD\u201917 (2017)","DOI":"10.1145\/3035918.3035939"},{"key":"602_CR12","volume-title":"Cohesive Subgraph Computation Over Large Sparse Graphs. Springer Series in the Data Sciences","author":"L Chang","year":"2018","unstructured":"Chang, L., Qin, L.: Cohesive Subgraph Computation Over Large Sparse Graphs. Springer Series in the Data Sciences. Springer, Berlin (2018)"},{"key":"602_CR13","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00453-012-9632-8","volume":"66","author":"L Chang","year":"2012","unstructured":"Chang, L., Yu, J.X., Qin, L.: Fast maximal cliques enumeration in sparse graphs. Algorithmica 66, 173 (2012)","journal-title":"Algorithmica"},{"key":"602_CR14","doi-asserted-by":"crossref","unstructured":"Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: Proceedings of SIGMOD\u201913 (2013)","DOI":"10.1145\/2463676.2465323"},{"issue":"4","key":"602_CR15","doi-asserted-by":"publisher","first-page":"21:1\u201321:34","DOI":"10.1145\/2043652.2043654","volume":"36","author":"J Cheng","year":"2011","unstructured":"Cheng, J., Ke, Y., Fu, A.W.-C., Yu, J.X., Zhu, L.: Finding maximal cliques in massive networks. ACM Trans. Database Syst. 36(4), 21:1\u201321:34 (2011)","journal-title":"ACM Trans. Database Syst."},{"issue":"1","key":"602_CR16","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."},{"key":"602_CR17","unstructured":"Cohen, J.: Trusses: cohesive subgraphs for social network analysis. National Security Agency Technical Report (2008)"},{"key":"602_CR18","doi-asserted-by":"crossref","unstructured":"Danisch, M., Balalau, O.D., Sozio, M.: Listing k-cliques in sparse real-world graphs. In: Proceedings of WWW\u201918, pp. 589\u2013598 (2018)","DOI":"10.1145\/3178876.3186125"},{"key":"602_CR19","doi-asserted-by":"crossref","unstructured":"Deveci, M., Boman, E.G., Devine, K.D., Rajamanickam, S.: Parallel graph coloring for manycore architectures. In: Proceedings of IPDPS\u201916, pp. 892\u2013901 (2016)","DOI":"10.1109\/IPDPS.2016.54"},{"key":"602_CR20","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Blelloch, G.E., Shun, J.: Julienne: a framework for parallel graph algorithms using work-efficient bucketing. In: Proceedings of SPAA\u201917, pp. 293\u2013304 (2017)","DOI":"10.1145\/3087556.3087580"},{"key":"602_CR21","first-page":"18","volume":"12","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. Algorithm. 12, 18 (2013)","journal-title":"ACM J. Exp. Algorithm."},{"issue":"5","key":"602_CR22","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/1552285.1552286","volume":"56","author":"FV Fomin","year":"2009","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56(5), 12 (2009)","journal-title":"J. ACM"},{"issue":"3","key":"602_CR23","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1016\/0743-7315(92)90072-U","volume":"14","author":"N Funabiki","year":"1992","unstructured":"Funabiki, N., Takefuji, Y., Lee, K.C.: A neural network model for finding a near-maximum clique. J. Parallel Distrib. Comput. 14(3), 340\u2013344 (1992)","journal-title":"J. Parallel Distrib. Comput."},{"key":"602_CR24","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, Berkeley, CA, USA (1984)"},{"issue":"1","key":"602_CR25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/BF02523693","volume":"18","author":"MM Halld\u00f3rsson","year":"1997","unstructured":"Halld\u00f3rsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145\u2013163 (1997)","journal-title":"Algorithmica"},{"key":"602_CR26","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n$${}^{\\text{1-epsilon}}$$. In: Proceedings of FOCS\u201996, pp. 627\u2013636 (1996)"},{"key":"602_CR27","doi-asserted-by":"crossref","unstructured":"Hespe, D., Lamm, S., Schulz, C., Strash, D.: WeGotYouCovered: the winning solver from the PACE 2019 implementation challenge, vertex cover track. CoRR abs\/1908.06795 (2019)","DOI":"10.1137\/1.9781611976229.1"},{"issue":"4","key":"602_CR28","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347\u2013360 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"602_CR29","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of CCC\u201972, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"602_CR30","doi-asserted-by":"crossref","unstructured":"Kim, H., Lee, J., Bhowmick, S.S., Han, W.-S., Lee, J.-H., Ko, S., Jarrah, M.H.A.: DUALSIM: parallel subgraph enumeration in a massive graph on a single machine. In: Proceedings of SIGMOD\u201916 (2016)","DOI":"10.1145\/2882903.2915209"},{"issue":"3","key":"602_CR31","first-page":"217","volume":"10","author":"L Longbin Lai","year":"2016","unstructured":"Longbin Lai, L., Qin, X.L., Zhang, Y., Chang, L.: Scalable distributed subgraph enumeration. PVLDB 10(3), 217\u2013228 (2016)","journal-title":"PVLDB"},{"key":"602_CR32","unstructured":"Lamm, S., Sanders, P., Schulz, C., Strash, D., Werneck, R.F.: Finding near-optimal independent sets at scale. In: Proceedings of ALENEX\u201916, pp. 138\u2013150 (2016)"},{"key":"602_CR33","doi-asserted-by":"crossref","unstructured":"Li, C.-M., Fang, Z., Xu, K.: Combining maxsat reasoning and incremental upper bound for the maximum clique problem. In: Proceedings of ICTAI\u201913 (2013)","DOI":"10.1109\/ICTAI.2013.143"},{"key":"602_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cor.2017.02.017","volume":"84","author":"C-M Li","year":"2017","unstructured":"Li, C.-M., Jiang, H., Many\u00e0, F.: On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem. Comput. OR 84, 1\u201315 (2017)","journal-title":"Comput. OR"},{"issue":"11","key":"602_CR35","first-page":"1538","volume":"10","author":"C Lu","year":"2017","unstructured":"Lu, C., Yu, J.X., Wei, H., Zhang, Y.: Finding the maximum clique in massive graphs. PVLDB 10(11), 1538\u20131549 (2017)","journal-title":"PVLDB"},{"key":"602_CR36","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/1471-2105-10-205","volume":"10","author":"T Matsunaga","year":"2009","unstructured":"Matsunaga, T., Yonemori, C., Tomita, E., Muramatsu, M.: Clique-based data mining for related genes in a biomedical database. BMC Bioinform. 10, 44 (2009)","journal-title":"BMC Bioinform."},{"issue":"3","key":"602_CR37","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"issue":"3","key":"602_CR38","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01098364","volume":"4","author":"PM Pardalos","year":"1994","unstructured":"Pardalos, P.M., Xue, J.: The maximum clique problem. J. Glob. Optim. 4(3), 301\u2013328 (1994)","journal-title":"J. Glob. Optim."},{"issue":"4\u20135","key":"602_CR39","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1080\/15427951.2014.986778","volume":"11","author":"B Pattabiraman","year":"2015","unstructured":"Pattabiraman, B., Patwary, M.M.A., Gebremedhin, A.H., Liao, W., Choudhary, A.N.: Fast algorithms for the maximum clique problem on massive graphs with applications to overlapping community detection. Internet Math. 11(4\u20135), 421\u2013448 (2015)","journal-title":"Internet Math."},{"issue":"2","key":"602_CR40","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/s10732-010-9131-5","volume":"17","author":"W Pullan","year":"2011","unstructured":"Pullan, W., Mascia, F., Brunato, M.: Cooperating local search for the maximum clique problem. J. Heuristics 17(2), 181\u2013199 (2011)","journal-title":"J. Heuristics"},{"key":"602_CR41","doi-asserted-by":"crossref","unstructured":"Rokos, G., Gorman, G., Kelly, P.H.J.: A fast and scalable graph coloring algorithm for multi-core and many-core architectures. In: Proceedings of Euro-Par\u201915, pp. 414\u2013425 (2015)","DOI":"10.1007\/978-3-662-48096-0_32"},{"issue":"5","key":"602_CR42","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1137\/14100018X","volume":"37","author":"RA Rossi","year":"2015","unstructured":"Rossi, R.A., Gleich, D.F., Gebremedhin, A.H.: Parallel maximum clique algorithms with applications to network analysis. SIAM J. Sci. Comput. 37(5), 13 (2015)","journal-title":"SIAM J. Sci. Comput."},{"key":"602_CR43","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1186\/s40537-018-0121-z","volume":"5","author":"RA Rossi","year":"2018","unstructured":"Rossi, R.A., Zhou, R.: Graphzip: a clique-based sparse graph compression method. J. Big Data 5, 10 (2018)","journal-title":"J. Big Data"},{"issue":"1","key":"602_CR44","first-page":"43","volume":"12","author":"AE Sariy\u00fcce","year":"2018","unstructured":"Sariy\u00fcce, A.E., Seshadhri, C., Pinar, A.: Local algorithms for hierarchical dense subgraph discovery. PVLDB 12(1), 43\u201356 (2018)","journal-title":"PVLDB"},{"key":"602_CR45","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.cor.2015.07.013","volume":"66","author":"PS Segundo","year":"2016","unstructured":"Segundo, P.S., Lopez, A., Pardalos, P.M.: A new exact maximum clique algorithm for large and massive sparse graphs. Comput. Oper. Res. 66, 81\u201394 (2016)","journal-title":"Comput. Oper. Res."},{"issue":"3","key":"602_CR46","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269\u2013287 (1983)","journal-title":"Soc. Netw."},{"key":"602_CR47","doi-asserted-by":"crossref","unstructured":"Serafini, M., De\u00a0Francisci Morales, G., Siganos, G.: Qfrag: distributed graph search via subgraph isomorphism. In: Proceedings of SoCC\u201917 (2017)","DOI":"10.1145\/3127479.3131625"},{"key":"602_CR48","doi-asserted-by":"crossref","unstructured":"Tomita, E.: Efficient algorithms for finding maximum and maximal cliques and their applications. In: Proceedings of WALCOM\u201917, pp. 3\u201315 (2017)","DOI":"10.1007\/978-3-319-53925-6_1"},{"key":"602_CR49","doi-asserted-by":"crossref","unstructured":"Tomita, E., Sutani, Y., Higashi, T., Shinya T., Mitsuo W.: A simple and faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of WALCOM\u201910, pp. 191\u2013203 (2010)","DOI":"10.1007\/978-3-642-11440-3_18"},{"issue":"1","key":"602_CR50","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."},{"key":"602_CR51","doi-asserted-by":"crossref","unstructured":"Tomita, E., Yoshida, K., Hatta, T., Nagao, A., Ito, H., Wakatsuki, M.: A much faster branch-and-bound algorithm for finding a maximum clique. In: Proceedings of FAW\u201916, pp. 215\u2013226 (2016)","DOI":"10.1007\/978-3-319-39817-4_21"},{"issue":"1","key":"602_CR52","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1109\/TKDE.2018.2833070","volume":"31","author":"D Wen","year":"2019","unstructured":"Wen, D., Qin, L., Zhang, Y., Lin, X., Yu, J.X.: I\/O efficient core graph decomposition: application to degeneracy ordering. IEEE Trans. Knowl. Data Eng. 31(1), 75\u201390 (2019)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"602_CR53","unstructured":"Xiang, J., Guo, C., Aboulnaga, A.: Scalable maximum clique computation using mapreduce. In: Proceedings of ICDE\u201913, pp. 74\u201385 (2013)"},{"issue":"6","key":"602_CR54","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1016\/j.jplph.2010.09.010","volume":"168","author":"X Zheng","year":"2011","unstructured":"Zheng, X., Liu, T., Yang, Z., Wang, J.: Large cliques in arabidopsis gene coexpression network and motif discovery. J. Plant Physiol. 168(6), 611\u2013618 (2011)","journal-title":"J. Plant Physiol."}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00602-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-020-00602-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-020-00602-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T09:38:28Z","timestamp":1613295508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-020-00602-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,15]]},"references-count":54,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["602"],"URL":"https:\/\/doi.org\/10.1007\/s00778-020-00602-z","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,15]]},"assertion":[{"value":"13 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}