Bài toán tập độc lập trong đồ thị có bậc bị chặn

: 08h30, ngày 24/04/2017 (Thứ Hai)

: P104 D3, ĐH BKHN

: Seminar Toán rời rạc

: Lê Chí Ngọc

: ĐH Bách Khoa Hà Nội

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

Báo cáo trình bày về bài toán tập độc lập trong đồ thị có bậc bị chặn. Với hạn chế này, một số lớp đồ thị sẽ có lời giải trong thời gian đa thức. Báo cáo cũng trình bày về một phương pháp chứng minh tính NP-khó của bài toán trong một số trường hợp.


Đánh giá bài viết


Xem thêm