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ố

Thành Huấn Phan1, Thị Châu Ái Huỳnh2, Lê Sa Lin Châu3
1Đại học Quốc gia TP. Hồ Chí Minh,Việt Nam
2Khoa Kỹ thuật công nghệ, Trường Đại học Văn Hiến
3Khoa Công nghệ thông tin - truyền thông, Trường Cao đẳng Kinh tế - Kỹ thuật Cần Thơ

Tóm tắt

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.

Từ khóa

#Clique lớn nhất #tiếp cận heuristic #NP-complete #Maximum Clique #Heuristic

Tài liệu tham khảo