A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem

Sun Yuan Hsieh, Shih Shun Kao, Yu Sheng Lin

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)


The maximum k-plex problem is intended to relax the clique definition with maximum cardinality. It helps people understand the structures of networks by considering them a problem of graph clustering; therefore, it is a useful model for social network analysis. In this paper, we propose a swap-based heuristic algorithm for the maximum k-plex problem. Starting with a randomly selected solution, we use three types of swap operators to enlarge our current solution in different situations. The results of experiments conducted on various graphs from two benchmarks demonstrated that our proposed algorithm achieved desirable performance on specific graphs compared with other algorithms.

Original languageEnglish
Article number8794502
Pages (from-to)110267-110278
Number of pages12
JournalIEEE Access
Publication statusPublished - 2019

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Materials Science(all)
  • Engineering(all)


Dive into the research topics of 'A Swap-Based Heuristic Algorithm for the Maximum k-Plex Problem'. Together they form a unique fingerprint.

Cite this