: 15h00, ngày 24/03/2023 (Thứ Sáu)
: P104 D3, ĐH Bách Khoa Hà Nội
: 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
Finding a minimum dominating set in graphs is NP-hard in general. In this research, we will revise the NP-hardness results and continue with the developing a new technique, so-called decreasing graph, to show that the problem can be solved in polynomial time in some graph classes. These results are extended of some previous ones.