About Maximum Independent Set Problem

: 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.

Đánh giá bài viết

Xem thêm