Zhichao Xie

A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing e…