Một số phương pháp Heuristic cho bài toán Tập thống trị

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

Bài toán tìm tập thống trị (Dominating Set) có lực lượng nhỏ nhất trong đồ thị có rất nhiều ứng dụng trong thực hành, ví dụ như các vấn đề liên quan đến chuỗi cung ứng (logistic), giao thông, truyền tin. Bài toán đã được chứng minh là thuộc phân lớp NP-khó (không có thuật toán chạy được trong thời gian đa thức trong trường hợp tổng quát, trừ phi P = NP). Báo cáo trình bày về một số thuật toán Heuristic (cho lời giải là tập thống trị cực đại trong thời gian đa thức) cho bài toán này. Ứng dụng của các thuật toán cũng như một số hướng phát triển tiềm năng trong tương lai.