Bài toán Clique

Bài toán clique lớn nhất (Maximum clique problem) là bài toán tối ưu tổ hợp được ứng dụng trong nhiều lĩnh vực như mạng xã hội, tin sinh học, tài chính, lập lịch và đã được chứng minh là bài toán thuộc lớp NP-Hard. Nghiên cứu này đề xuất giải thuật bầy ong giải bài toán clique lớn nhất dựa trên hệ thống dữ liệu thực nghiệm chuẩn DIMACS gồm 37 bộ dữ liệu thực nghiệm.

9p viedison 13-04-2022 29 2   Download

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.

8p viplato 05-04-2022 28 3   Download

Bài viết trình bày việc cải tiến hai thuật toán dạng heuristic giải bài toán clique lớn nhất; Các thuật toán cải tiến của chúng tôi dựa trên hai thuật toán heuristic hiệu quả hiện biết. Đã cài đặt và thực nghiệm các thuật toán này trên 78 bộ dữ liệu trong hai hệ thống dữ liệu thực nghiệm chuẩn DIMACS và BHOSLIB.

9p vijihyo2711 25-09-2021 22 2   Download

Luận văn trình bày về bài toán Clique Editing, và chứng minh tính NP-đầy đủ của bài toán, sau đó sẽ tìm hiểu lớp bài toán FPT và chứng minh bài toán Clique Editing thuộc lớp FPT. Mời các bạn tham khảo!

53p elephantcarrot 02-07-2021 45 3   Download

Bài toán clique lớn nhất là một bài toán kinh điển của lý thuyết đồ thị và có nhiều ứng dụng. Nhiều vấn đề trong các mạng xã hội, sinh học, tài chính được giải quyết thông qua bài toán tìm kiếm các clique trong đồ thị. Clique và phân vùng clique cũng được sử dụng như một công cụ phân cụm hay phân loại dữ liệu.

5p cumeo2425 02-07-2018 131 3   Download