Open AccessTiế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ố
Author(s) -
Thành Huấn Phan,
Thị Châu Ái Huỳnh,
Lê Sa Lin Châu
Publication year - 2021
Publication title -
công trình nghiên cứu công nghệ thông tin truyền thông
Language(s) - Vietnamese
Resource type - Journals
ISSN - 1859-3526
DOI - 10.32913/mic-ict-research-vn.v2021.n1.964
Subject(s) - chemistry , stereochemistry
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ĩnhvự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íchhai 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ớnnhấ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.