Details of Research Outputs

TitleImproving Maximum k-Plex Solver via Second-Order Reduction and Graph Color Bounding
Author (Name in English or Pinyin)
Yi Zhou; Shan Hu; Mingyu Xia; 付樟华
Date Issued2020-12-02
Conference NameAAAI
Source PublicationVirtual Conference
Conference DateFebruary 2, 2021 - February 9, 2021
Conference Place线上
Publication PlacePALO ALTO
PublisherAssociation for the Advancement of Artificial Intelligence
AbstractIn a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex. © 2021, Association for the Advancement of Artificial Intelligence ( All rights reserved.
KeywordArtificial intelligence Graph theory Community detection Exact algorithms First order Order graph Pre-processing method Real-world Real-world graphs Reduction rules Second order reductions Vertex set
Indexed ByEI ; CPCI-S
WOS Research AreaComputer Science ; Education & Educational Research
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Interdisciplinary Applications ; Education, Scientific Disciplines
WOS IDWOS:000681269804015
EI Accession Number20222012121622
EI Classification Number723.4 Artificial Intelligence - 921.4 Combinatorial Mathematics, Includes Graph Theory, Set Theory
Original Document TypeConference article (CA)
Education discipline科技类
Published range国内外公开发行
Data SourceEI
Citation statistics
Document TypeConference paper
CollectionInstitute of Robotics and Intelligent Manufacturing
School of Science and Engineering
Corresponding Author付樟华
Corresponding Author AffilicationInstitute of Robotics and Intelligent Manufacturing
Recommended Citation
GB/T 7714
Yi Zhou,Shan Hu,Mingyu Xiaet al. Improving Maximum k-Plex Solver via Second-Order Reduction and Graph Color Bounding[C]. PALO ALTO:Association for the Advancement of Artificial Intelligence,2020:12453-12460.
Files in This Item:
There are no files associated with this item.
Related Services
Usage statistics
Google Scholar
Similar articles in Google Scholar
[Yi Zhou]'s Articles
[Shan Hu]'s Articles
[Mingyu Xia]'s Articles
Baidu academic
Similar articles in Baidu academic
[Yi Zhou]'s Articles
[Shan Hu]'s Articles
[Mingyu Xia]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Yi Zhou]'s Articles
[Shan Hu]'s Articles
[Mingyu Xia]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.