Người báo cáo: Lê Chí Ngọc
Thời gian: 9h30 Thứ 5, 23/4/2015
Địa điểm: Phòng 201, Nhà A5, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy Hà Nội
Tóm tắt: 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. | 
