Participant Information :: Administrator

Total posts : 12 , Total comments : 0

Full name : Administrator
Preferred Name : Sergiy
Homepage : http://ise.tamu.edu/people/faculty/butenko
Email :

Organization : Texas A&M University
Address Line 1 : 236E Zachry Engineering Center
Address Line 2 : TAMU-3131
City, State, ZIP, Country : College Station, TX77843-3131, USA

Title, authors and abstract of the talk
This paper introduces and studies the {\em maximum $k$-plex roblem}, which arises in social network analysis and has wider pplicability in several important areas employing graph-based data mining. After establishing NP-completeness of the decision version of the problem on arbitrary graphs, an integer programming formulation is presented followed by a polyhedral study to identify combinatorial valid inequalities and facets. A branch-and-cut algorithm is implemented and tested on proposed benchmark instances. An algorithmic approach is developed exploiting the graph-theoretic properties of a $k$-plex, that is
effective in solving the problem to optimality on very large, sparse graphs such as the \emph{power law graphs} frequently encountered in the applications of interest.