{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:57:43Z","timestamp":1773392263598,"version":"3.50.1"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.<\/jats:p>","DOI":"10.24963\/ijcai.2018\/201","type":"proceedings-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:49:10Z","timestamp":1530769750000},"page":"1449-1455","source":"Crossref","is-referenced-by-count":19,"title":["An Exact Algorithm for Maximum k-Plexes in Massive Graphs"],"prefix":"10.24963","author":[{"given":"Jian","family":"Gao","sequence":"first","affiliation":[{"name":"College of Information Science and Technology, Dalian Maritime University, China"},{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiejiang","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minghao","family":"Yin","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rong","family":"Chen","sequence":"additional","affiliation":[{"name":"College of Information Science and Technology, Dalian Maritime University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yiyuan","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Information Technology, Northeast Normal University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10584","event":{"name":"Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}","theme":"Artificial Intelligence","location":"Stockholm, Sweden","acronym":"IJCAI-2018","number":"27","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2018,7,13]]},"end":{"date-parts":[[2018,7,19]]}},"container-title":["Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T05:50:50Z","timestamp":1530769850000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2018\/201"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2018\/201","relation":{},"subject":[],"published":{"date-parts":[[2018,7]]}}}