Trong bài viết 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. | Các công trình nghiên cứu phát triển và ứng dụng CNTT và Truyền thông Tiếp cận Heuristic giải bài toán Clique lớn nhất trên đơn đồ thị vô hướng không có trọng số Phan Thành Huấn1 Huỳnh Thị Châu Ái2 Châu Lê Sa Lin3 1 Đại học Quốc gia Tp. Hồ Chí Minh 2 Khoa Kỹ thuật Công nghệ Trường Đại học Văn Hiến 3 Khoa Công nghệ Thông tin - truyền thông Trường Cao đẳng Kinh tế - Kỹ thuật Cần Thơ Tác giả liên hệ Phan Thành huấn huanphan@ Ngày nhận bài 15 04 2021 ngày sửa chữa 01 06 2021 ngày duyệt đăng 12 06 2021 Định danh DOI 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ĩ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. Từ khóa clique lớn nhất tiếp cận Heuristic NP-complete. Title Heuristic Approach for Solving the Maximum Clique Problem on Simple Undirected and Unweighted Graph Abstract The Maximum Clique Problem is the problem of finding the largest subset of vertices in a simple undirected graph such that two distinct vertices in it are always adjacent. This is a well-known NP-complete problem widely applied in the fields of data mining network analysis information retrieval medicine education and many other fields related to World Wide Web. There are many approaches to solving the Maximum Clique problem such as .
