WEEKLY ACTIVITIES

Algorithms for the Maximum Independent Set Problem (Part 2)
Speaker: Le Chi Ngoc

Time: 9h30, Thursday,  April 9, 2015

Location: Room 201, Building A5, Institute of Mathematics, 18 Hoang Quoc Viet, Cau Giay, Ha Noi

Abstract: The thesis focuses mainly on the maximum independent set (MIS) problem. Somerelated graph theoretical combinatorial problems are also considered. We study their complexity in hereditary graph classes, i.e. in graph classes de ned by a set F of forbidden induced subgraphs. 

Through considering some general approach, we exhibit several cases where the problem admits a polynomial-time solution, for example subclasses of S2;j;k-free graphs and subclasses of Si;j;k-free subcubic graphs. Our algorithms are based on various approaches, for example augmenting approaches, graph transformations, classical sequential greedy heuristics, clique separator, and some hybrid methods.

We also extend the augmenting approach for some other related problems.

Back