Degree Based Generalizations of Cliques and Stable Sets
Illya V. Hicks (Rice University)

In this talk, we will explore the maximum k-plex problem and the maximum co-k-plex problem, degree based generalizations of cliques and stable sets, respectively. The maximum k-plex problem was first introduced in social network analysis, but also has several other important applications in wireless networks, telecommunications, and data mining. The first part of the talk covers a branch-and-cut implementation for the maximum k-plex problem while the second part covers co-2-plex analogues of some well-known inequalities for the stable set polytope.

Colloquium, Department of Mathematics, Rice University
January 31, 2008, HB 227, 4:00PM


Back to colloquium page