On Minimum Dominating Problem: NP-hardness and Polynomial Results

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


Đánh giá bài viết


Xem thêm