Dominating sets in some families of graphs: NP-hardness and Polynomial results.

: 15h00, ngày 23/10/2024 (Thứ Tư)

: P104 D3, ĐH Bách Khoa Hà Nội

: Seminar Toán rời rạc

: Phạm Lê Vũ

: Khoa Toán Tin, Đại học Bách Khoa Hà Nội

Tóm tắt báo cáo

This presentation investigates the problem of finding minimum dominating sets in graphs. We establish the NP-hardness of the problem for several graph classes, demonstrating its computational complexity.


Đánh giá bài viết


Xem thêm