: 15h30, ngày 22/10/2022 (Thứ Bảy)
: P104 D3
: Seminar Toán rời rạc
: Lê Chí Ngọc
: Viện Toán ứng dụng và Tin học, ĐH Bách Khoa Hà Nội
Tóm tắt báo cáo
Maximum Independent Set Problem asks for a vertex subset in a graph of maximum cardinality such that there is no edge among us. It is known that the problem is NP-hard in general, i.e. there is no hope about some polynomial time complexity algorithm for solving the problem unless P = NP in general case. In this talk, we will present some up-to-date results, as well as review on some methods for tackling the problem.