{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:06:26Z","timestamp":1761599186080,"version":"3.37.3"},"reference-count":37,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2019,8]]},"abstract":"<jats:p> As a relaxation of clique in graph theory, k-plex is a powerful tool for analyzing social networks and identifying cohesive structures in graphs. Recently, more and more researchers have concentrated on the algorithms for the maximum k-plex problem. Among those algorithms, a branch-and-bound algorithm proposed very recently shows a good performance on solving large sparse graphs, but does not work well on social networks. In this paper, we propose two novel vertex selection heuristic strategies for branching. The first one employs historical information of vertex reduction, and the second one is a combination of the first heuristic and the degree-based approach. Intensive experiments on Facebook benchmark show that the algorithm combining our heuristics outperforms the state-of-the-art algorithms. <\/jats:p>","DOI":"10.1142\/s0218213019500155","type":"journal-article","created":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T01:57:22Z","timestamp":1567130242000},"page":"1950015","source":"Crossref","is-referenced-by-count":2,"title":["Vertex Selection Heuristics in Branch-and-Bound Algorithms for the Maximum <i>k<\/i>-Plex Problem"],"prefix":"10.1142","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1911-1731","authenticated-orcid":false,"given":"Kuixian","family":"Wu","sequence":"first","affiliation":[{"name":"College of Information Science and Technology, Dalian Maritime University, Dalian, 116026, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1962-0173","authenticated-orcid":false,"given":"Jian","family":"Gao","sequence":"additional","affiliation":[{"name":"College of Information Science and Technology, Dalian Maritime University, Dalian, 116026, China"}]},{"given":"Rong","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Information Science and Technology, Dalian Maritime University, Dalian, 116026, China"}]},{"given":"Xianji","family":"Cui","sequence":"additional","affiliation":[{"name":"College of Information and Communication Engineering, Dalian Minzu University, Dalian, 116600, China"}]}],"member":"219","published-online":{"date-parts":[[2019,8,29]]},"reference":[{"key":"p_1","first-page":"1240","author":"Cheng J.","year":"2012","journal-title":"China"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.06.001"},{"key":"p_4","first-page":"8107","author":"Li R.","year":"2018","journal-title":"Louisiana, USA"},{"key":"p_5","first-page":"1412","author":"Cai S.","year":"2018","journal-title":"Sweden"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"p_7","first-page":"143","author":"Pattillo J.","year":"2012","journal-title":"New York"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1007\/s11276-005-1769-9"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1145\/959242.959249"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.05.026"},{"key":"p_11","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"p_13","first-page":"278","author":"Tomita E.","year":"2003","journal-title":"France"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.05.017"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.03.020"},{"key":"p_17","first-page":"568","author":"Cai S.","year":"2016","journal-title":"USA"},{"key":"p_18","first-page":"805","author":"Wang Y.","year":"2016","journal-title":"Arizona, USA"},{"key":"p_19","first-page":"747","author":"Cai S.","year":"2015","journal-title":"Argentina"},{"key":"p_20","first-page":"303","author":"Fang Z.","year":"2014","journal-title":"Czech Republic"},{"key":"p_21","first-page":"830","author":"Jiang H.","year":"2017","journal-title":"California, USA"},{"key":"p_22","first-page":"1338","author":"Jiang H.","year":"2018","journal-title":"Louisiana, USA"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2014.07.006"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-016-0009-9"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.05.071"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1242-y"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"p_30","first-page":"16","author":"Du N.","year":"2007","journal-title":"USA"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9391-5"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.05.005"},{"key":"p_35","first-page":"919","author":"Xiao M.","year":"2017","journal-title":"California, USA"},{"key":"p_36","first-page":"1449","author":"Gao J.","year":"2018","journal-title":"Sweden"},{"key":"p_37","first-page":"41","author":"Smith B. M.","year":"1998","journal-title":"UK"},{"key":"p_38","first-page":"4292","author":"Rossi R.","year":"2015","journal-title":"Texas, USA"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213019500155","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T01:57:46Z","timestamp":1567130266000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213019500155"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8]]},"references-count":37,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2019,8,29]]},"published-print":{"date-parts":[[2019,8]]}},"alternative-id":["10.1142\/S0218213019500155"],"URL":"https:\/\/doi.org\/10.1142\/s0218213019500155","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"type":"print","value":"0218-2130"},{"type":"electronic","value":"1793-6349"}],"subject":[],"published":{"date-parts":[[2019,8]]}}}