{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T17:43:33Z","timestamp":1786211013162,"version":"3.56.0"},"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":[[2023,8]]},"abstract":"<jats:p>A k-plex of a graph G is an induced subgraph in which every vertex has at most k-1 nonadjacent vertices. The Maximum k-plex Problem (MKP) consists in finding a k-plex of the largest size, which is NP-hard and finds many applications. Existing exact algorithms mainly implement a branch-and-bound approach and improve performance  by integrating effective upper bounds and graph reduction rules. In this paper, we propose a refined upper bound, which can derive a tighter upper bound than existing methods,  and an inprocessing strategy, which performs graph reduction incrementally. We implement a new BnB algorithm for MKP that employs the two components to reduce the search space.  Extensive experiments show that both the refined upper bound and the inprocessing strategy are very efficient in the  reduction of search space. The new algorithm outperforms the state-of-the-art algorithms on the tested benchmarks significantly.<\/jats:p>","DOI":"10.24963\/ijcai.2023\/623","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"5613-5621","source":"Crossref","is-referenced-by-count":7,"title":["A Refined Upper Bound and Inprocessing for the Maximum K-plex Problem"],"prefix":"10.24963","author":[{"given":"Hua","family":"Jiang","sequence":"first","affiliation":[{"name":"Engineering Research Center of Cyberspace & School of Software, Yunnan University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fusheng","family":"Xu","sequence":"additional","affiliation":[{"name":"Engineering Research Center of Cyberspace & School of Software, Yunnan University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhifei","family":"Zheng","sequence":"additional","affiliation":[{"name":"Engineering Research Center of Cyberspace & School of Software, Yunnan University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bowen","family":"Wang","sequence":"additional","affiliation":[{"name":"Engineering Research Center of Cyberspace & School of Software, Yunnan University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Zhou","sequence":"additional","affiliation":[{"name":"Engineering Research Center of Cyberspace & School of Software, Yunnan University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","theme":"Artificial Intelligence","location":"Macau, SAR China","acronym":"IJCAI-2023","number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2023,8,19]]},"end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:52:32Z","timestamp":1691743952000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/623"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/623","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}