Tiếp cận Heuristic giải bài toán Clique lớn nhất trên đồ thị đơn vô hướng không trọng số
Heuristic Approach for Solving the Maximum Clique Problem on Simple Undirected and Unweighted Graph
Abstract
Bài toán Clique lớn nhất (Maximum Clique Problem) là bài toán tìm tập con lớn nhất của tập đỉnh trong đơn
đồ thị vô hướng, sao cho hai đỉnh phân biệt trong nó luôn kề nhau. Đây là bài toán nổi tiếng thuộc lớp NP-complete, được
ứng dụng nhiều trong các lĩnh vực khai thác dữ liệu, phân tích mạng, truy xuất thông tin, y học, giáo dục và nhiều lĩnh
vực khác liên quan đến mạng lưới toàn cầu. Có nhiều cách tiếp cận giải bài toán Clique lớn nhất như quy hoạch động,
nhánh-cận, heuristic hay meta-heuristic – cho lời giải chính xác hay xấp xỉ. Trong bài báo này, nhóm tác giả phân tích
hai thuật giải tiếp cận heuristic gần đây và đề xuất các heuristic tăng độ chính xác của lời giải cho bài toán Clique lớn
nhất. Phần thực nghiệm, nhóm tác giả so sánh chất lượng lời giải của thuật giải đề xuất trên 10 bộ dữ liệu từ DIMACS.
