We investigate the problem of extracting a subset of maximal cliques inside an undirected graph. This problem is considered as a NP-complete problem. In this work, we propose a heuristic algorithm that treats the above problem. In our algorithm, undirected graph is represented using the adjacency-list. Next, this representation is transformed into a new form so-called transaction database that is very familiar in data mining domain. Based on the new representation, we are able to count the frequency of subset of vertices inside undirected graph which is used to extract a set of maximal candidates that become possibly maximal cliques. Our experimental results show that this algorithm maintains a reasonable threshold in order to control its complexity.
224-C1, Hanoi University of Science and Technology 1 Dai Co Viet, Hai Ba Trung, Hanoi, Vietnam Tel: +84 (024) 3623.0949 | email: email@example.com
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ Giấy phép số37/GP-BTTTT (15/01/2021) Giấy phép sửa đổi, bổ sung số140/GP-BTTTT (05/3/2021) Đơn vị cấp phép:Bộ Thông tin và Truyền thông Cơ quan chủ quản:Trường Đại học Bách Khoa Hà Nội Phó tổng biên tập phụ trách:GS. Đinh Văn Phong