Speaker:

Yi Zhou (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• March 8, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

In the field of graph mining, the k-plex is a well-known extension of the clique model. A k-plex is nearly a clique except that each vertex is allowed to be not adjacent to at most k vertices, with k being a positive integer. When k=1, a k-plex is equivalent to a clique. Fundamental problems related to the k-plex include how to enumerate all maximal k-plexes and how to find the maximum k-plexes in a given graph. In this talk, I will present some of our recent results on these problems from the perspective of algorithm engineering. I will also introduce how techniques in the design of exact and parameterized algorithms assist in the analysis of practical k-plex algorithms.