Bài toán Clique lớn nhất - Ứng dụng và những thách thức tính toán

Đàm Thanh Phương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 102(02): 9 - 13<br /> <br /> BÀI TOÁN CLIQUE LỚN NHẤT - ỨNG DỤNG<br /> VÀ NHỮNG THÁCH THỨC TÍNH TOÁN<br /> Đàm Thanh Phương*, Ngô Mạnh Tưởng, Khoa Thu Hoài<br /> Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên<br /> <br /> TÓM TẮT<br /> 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<br /> 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<br /> 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<br /> phân loại dữ liệu. Tuy nhiên các bài toán thực tế thường được mô hình hoá bằng đồ thị rất lớn và<br /> cần phải có bộ nhớ lưu trữ đủ lớn cho quá trình thực hiện các thuật toán. Qua bài báo này, chúng<br /> tôi sẽ thảo luận bốn ứng dụng và xác định những thách thức tính toán đến từ lý thuyết cũng như<br /> thực hành.<br /> Từ khoá: Cliques, tựa clique, phân vùng clique, tập độc lập, bài toán clique lớn nhất, bài toán tập<br /> độc lập lớn nhất.<br /> <br /> GIỚI THIỆU*<br /> Một đơn đồ thị vô hướng G là cặp<br /> (V , E ) bao gồm tập hữu hạn, khác rỗng các<br /> <br /> Với mỗi tập con S ⊂ V , đồ thị con sinh bởi<br /> S được<br /> định<br /> nghĩa<br /> là<br /> <br /> đỉnh V và tập hữu hạn ( có thể rỗng) các cạnh<br /> E ⊆ V × V là các cặp không có thứ tự hai<br /> phần tử phân biệt của V . Trong bài báo này,<br /> chúng ta chỉ xét các đơn đồ thị vô hướng như<br /> trên và để vắn tắt, sẽ gọi chung là đồ thị. Hai<br /> đỉnh u , v ∈ V được gọi là hai đỉnh kề nếu<br /> <br /> Một tập đỉnh S được gọi là một clique nếu<br /> G ( S ) là đồ thị đầy đủ. Chúng ta cũng phân<br /> <br /> ( u, v ) ∈ E , nghĩa là một cạnh của đồ thị. Một<br /> <br /> đồ thị được gọi là đầy đủ nếu có cạnh giữa hai<br /> đỉnh bất kỳ. Đồ thị bù của G là đồ thị<br /> <br /> ( )<br /> E = {( i, j ) i, j ∈ V , i ≠ j , ( i, j ) ∉ E} . Đồ thị<br /> <br /> G = V , E , có cùng tập đỉnh V và tập cạnh<br /> được gọi là liên thông nếu tồn tại đường đi<br /> giữa hai đỉnh bất kỳ. Các thành phần liên<br /> thông của đồ thị là các đồ thị con liên thông<br /> cực đại. Độ dài của đường đi dài nhất trong số<br /> tất cả các đường đi ngắn nhất giữa hai đỉnh<br /> bất kỳ được gọi là đường kính. Mật độ của đồ<br /> thị được xác định bởi giá trị: 2 E . Hai<br /> V<br /> <br /> 2<br /> <br /> −V<br /> <br /> đồ thị G1 = (V1 , E1 ) , G2 = (V2 , E2 ) được gọi<br /> là đẳng cấu nếu tồn tại một song ánh<br /> φ :V1 → V2 thoả mãn:<br /> :<br /> <br /> ( u, v ) ∈ E1 ⇔ (φ ( u ) , φ ( v ) ) ∈ E2 .<br /> <br /> *<br /> <br /> Tel: 0912 998749, Email: dtphuong@ictu.edu.vn<br /> <br /> G (S ) = (S, E ∩ S × S )<br /> <br /> biệt giữa clique cực đại là clique không thuộc<br /> bất cứ một clique nào rộng hơn nó, với clique<br /> lớn nhất là clique có số phần tử lớn nhất. Một<br /> tập đỉnh S được gọi là một tập độc lập (tập<br /> ổn định) nếu hai đỉnh bất kỳ của S không kề<br /> nhau. Định nghĩa clique có thể tổng quát hoá<br /> cho khái niệm tựa clique. Một tựa clique hay<br /> γ -clique của đồ thị là tập đỉnh Cγ thoả mãn<br /> <br /> ( ) là liên thông và có ít nhất<br /> <br /> đồ thị con G Cγ<br /> <br />  q ( q − 1) <br /> γ<br /> <br /> 2 <br /> <br /> <br /> (1)<br /> <br /> cạnh, trong đó q = Cγ và γ ∈ [ 0,1] . Trong<br /> <br /> ( )<br /> <br /> trường hợp đặc biệt, khi γ = 0 , G Cγ<br /> <br /> có<br /> <br /> thể không có cạnh nào và khi γ = 1 thì Cγ là<br /> một clique của G . Tô màu đồ thị là phân chia<br /> tập đỉnh thành các tập ổn định rời nhau. Trong<br /> khi phủ clique là phân vùng tập đỉnh thành<br /> các clique rời nhau. Sau đây, ta gọi một phủ<br /> clique là phân vùng clique.<br /> Bài toán clique lớn nhất là bài toán tìm clique<br /> lớn nhất trong đồ thị đã cho. Ta ký hiệu số<br /> phần tử của clique lớn nhất trong đồ thị G là<br /> 9<br /> <br /> Đàm Thanh Phương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> ω ( G ) và gọi là chỉ số clique. Tương tự bài<br /> toán tập ổn định lớn nhất là bài toán tìm tập<br /> ổn định có số phần tử lớn nhất trong đồ thị.<br /> Chỉ số ổn định là số phần tử của tập ổn định<br /> lớn nhất, ký hiệu là α ( G ) . Số màu hay sắc<br /> số của đồ thị χ ( G ) là số nhỏ nhất các tập ổn<br /> <br /> định cần để tô màu đồ thị. Tương tự, số nhỏ<br /> nhất các clique cần để phân vùng clique đồ thị<br /> G được gọi là chỉ số phủ clique và ký hiệu<br /> <br /> χ ( G ) . Bài toán clique lớn nhất và bài toán<br /> <br /> phủ clique là một trong 21 bài toán mà<br /> Richard Karp đã chứng minh là NP đầy đủ<br /> Nghĩa là, trừ khi P = NP, các thuật toán chính<br /> xác giải bài toán có thời gian tăng theo hàm<br /> mũ với số đỉnh của đồ thị.<br /> Vì một clique trong G cũng là một tập ổn<br /> định trong G nên ta có<br /> <br /> ( )<br /> <br /> α (G ) = ω G<br /> <br /> (2)<br /> <br /> Hơn nữa ta cũng có các kết quả sau:<br /> <br /> χ (G ) = χ G<br /> <br /> ( )<br /> <br /> (3)<br /> <br /> ω (G ) ≤ χ (G )<br /> <br /> (4)<br /> <br /> α (G ) ≤ χ (G )<br /> <br /> (5)<br /> <br /> Dễ thấy số tập ổn định cần thiết để phủ đồ thị<br /> bằng số clique cần thiết để phủ đồ thị bù nên<br /> ta có đẳng thức (3). Vì vậy việc tìm sắc số đồ<br /> thị và chỉ số phủ clique là tương đương và tuỳ<br /> thuộc vào ứng dụng ta sẽ sử dụng bài toán<br /> phù hợp. Hai trong các đỉnh của clique lớn<br /> nhất không thể nằm cùng trong một tập ổn<br /> định nào. Vì vậy để phân chia tập đỉnh của đồ<br /> thị thành các tập ổn định rời nhau thì số tập<br /> ổn định ít nhất phải bằng số đỉnh của clique<br /> lớn nhất. Từ đó ta có bất đẳng thức (4). Bất<br /> đẳng thức (5) có được từ (2), (3), (4) với chú ý<br /> rằng đồ thị bù của đồ thị G chính là đồ thị G .<br /> Trong bài báo này chúng tôi thảo luận về các<br /> thách thức tính toán liên quan đến clique, tựa<br /> clique và phân vùng clique phát sinh từ bốn<br /> ứng dụng: Đồ thị các cuộc gọi, lý thuyết mã,<br /> đối sánh cấu trúc phân tử và giả thuyết Keller.<br /> 10<br /> <br /> 102(02): 9 - 13<br /> <br /> ĐỒ THỊ CUỘC GỌI<br /> Các công ty điện thoại thường phải đối mặ<br /> với các tập dữ liệu khổng lồ. Ví dụ dữ liệu<br /> cuộc gọi đường dài của công ty AT&T trong<br /> năm 1999: xấp xỉ 300 triệu cuộc gọi một<br /> ngày, tương đương với yêu cầu không gian<br /> lưu trữ khoảng 20 terabytes một năm [1]. Việc<br /> phân tích tập dữ liệu này lại rất quan trọng<br /> cho công ty trong việc nghiên cứu mẫu khách<br /> hàng và tối ưu hoá hoạt động của họ.<br /> Cho một tập dữ liệu cuộc gọi trong một<br /> khoảng thời gian (ví dụ xếp từ các ngày đến<br /> các tháng). Chúng ta có thể xây dựng một đồ<br /> thị gọi là đồ thị cuộc gọi như sau: Mỗi người<br /> sử dụng điện thoại đại diện cho một đỉnh của<br /> đồ thị, mỗi cuộc gọi là một cạnh có hướng.<br /> Kết quả là ta được một đa đồ thị có hướng bởi<br /> vì một người A có thể gọi cho người B nhiều<br /> lần. Các tựa clique vô hướng của đồ thị này<br /> có thể cung cấp thông tin về nhóm người có<br /> mối liên kết cao.<br /> Đồ thị có hàng triệu đỉnh thường được gọi là<br /> đồ thị lớn. Ngay cả việc hiển thị trực quan<br /> trên màn hình hay các phân tích thống kê cơ<br /> bản là các nhiệm vụ khó khăn. Với các đồ thị<br /> rất lớn, chúng thường không phù hợp với bộ<br /> nhớ RAM của máy tính hoặc thậm chí vào bộ<br /> nhớ chính. Vì thế, thuật toán bộ nhớ mở rộng<br /> đã được phát triển. Đồ thị cuộc gọi có các tính<br /> chất quan trọng đặc biệt sau [2], [3]:<br /> - Đồ thị rất lớn, tới hàng triệu đỉnh.<br /> - Đồ thị có mật độ rất thấp, trong khoảng<br /> 0,0000001<br /> - Đồ thị thường không liên thông, mặc dù<br /> chứa thành phần liên thông lớn<br /> - Đường kính vô hướng thấp, trong khoảng<br /> <br /> log ( n )<br /> <br /> - Bậc vào d in và bậc ra d out của đỉnh phân<br /> phối theo luật: P ( din )<br /> <br /> và P ( d out )<br /> <br /> din−γ in với γ in ∈ [2, 3]<br /> <br /> − γ out<br /> d out<br /> với γ out < 2 , ở đây<br /> <br /> P ( d ) là tỷ số của số đỉnh có bậc d trên<br /> <br /> tổng số đỉnh của đồ thị.<br /> Trong [3], Abello đã nghiên cứu đồ thị cuộc<br /> gọi trong 1 ngày với các cuộc gọi cố định tại<br /> AT&T và nhận được một đồ thị cuộc gọi với<br /> <br /> Đàm Thanh Phương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 53 triệu đỉnh và 170 triệu cạnh. Để khai thác<br /> cấu trúc ở trên, tác giả đã phải thực hiện tiền<br /> xử lý mở rộng. Các phân tích thuật toán của<br /> đồ thị đó là rất quan trọng. Tuy nhiên, các<br /> thuật toán được biết đến không áp dụng tốt<br /> trên đồ thị như vậy. Điều này dẫn chúng ta<br /> đến thử thách đầu tiên.<br /> Thách thức 1 (Thuật toán cho các đồ thị<br /> cực lớn với mật độ rất thấp): Thiết kế một<br /> thuật toán hiệu quả cùng với tập dữ liệu cho<br /> bài toán γ -clique lớn nhất trong đồ thị lớn có<br /> các tính chất như đồ thị cuộc gọi.<br /> Các đồ thị tương tự đồ thị cuộc gọi có thế kể<br /> đến như đồ thị internet, đồ thị SMS, đồ thị từ<br /> mạng xã hội…<br /> ĐỒ THỊ TRONG LÝ THUYẾT MÃ<br /> Bài toán cần quan tâm là: gửi một thông điệp<br /> qua kênh truyền có độ nhiễu cao với độ tin<br /> cậy lớn nhất có thể. Trong lý thuyết mã,<br /> người ta mong muốn tìm được một mã nhị<br /> phân đủ lớn có thể khắc phục một số lỗi nhất<br /> định với kích thước đã cho của từ nhị phân.<br /> Với từ nhị phân thể hiện bởi véc tơ<br /> <br /> u ∈ ( 0,1) , ký hiệu Fe ( u ) là tập hợp tất cả<br /> các véc tơ có thể thu được từ u do một lỗi e<br /> n<br /> <br /> nào đó, chẳng hạn mất hoặc chuyển vị các bit.<br /> Chú ý rằng các phần từ của Fe ( u ) không nhất<br /> thiết có độ dài n vì có thể là kết quả của việc<br /> mất bit. Tập con C ⊆ ( 0,1) được gọi là mã<br /> n<br /> <br /> e<br /> nếu<br /> Fe ( u ) ∩ Fe ( v ) = ∅; ∀u , v ∈ C với u ≠ v .<br /> <br /> sửa<br /> <br /> lỗi<br /> <br /> Bài toán đặt ra là tìm tập mã sửa lỗi lớn nhất,<br /> nghĩa là số phần tử của C là lớn nhất.<br /> Xét đồ thị gồm tập đỉnh là tập tất cả các véc<br /> tơ nhị phân u ∈ ( 0,1) và có cạnh ( u , v ) khi<br /> n<br /> <br /> Fe ( u ) ∩ Fe ( v ) ≠ ∅ . Theo cách này, mỗi<br /> cạnh thể hiện sự xung đột với mã sửa lỗi e .<br /> Đồ thị như vậy được gọi là đồ thị xung đột.<br /> Theo cấu trúc của đồ thị, một mã sửa lỗi<br /> tương đương với một tập ổn định trong G .<br /> Vì vậy mã sửa lỗi lớn nhất có thể tìm được<br /> thông qua việc giải bài toán tập độc lập lớn<br /> nhất trong đồ thị G vừa đề cập.<br /> <br /> 102(02): 9 - 13<br /> <br /> Các cận dưới tốt của kích thước mã là điều có<br /> ý nghĩa đặc biệt cho các mã bất đối xứng,<br /> chẳng hạn như các mã sửa lỗi trong kênh Z (<br /> các thành phần khác không của mọi véc tơ có<br /> thể thay đổi từ 1 đến 0). Vì điều này, một số<br /> phương pháp phân vùng đã được đề xuất,<br /> bằng cách phân vùng tập ổn định nhỏ nhất<br /> trên đồ thị xung đột [4]. Việc tìm kiếm các<br /> cận dưới tốt cho kích thước mã như trên và<br /> thuật toán phân vùng tập ổn định phù hợp là<br /> một thách thức cần thiết phải giải quyết.<br /> Thách thức 2: (Thuật toán cho các đồ thị<br /> xung đột trong lý thuyết mã) Thiết kế thuật<br /> toán hiệu quả cho bài toán phân vùng tập ổn<br /> định tối thiểu phù hợp với đồ thị xung đột ứng<br /> dụng trong lý thuyết mã.<br /> Một số ví dụ khác trong đó phân vùng clique<br /> tối thiểu được sử dụng như những cận dưới là<br /> các bài toán phủ bắt buộc, trong đó tập các<br /> điểm yêu cầu phải được phủ bởi tập điểm<br /> tiềm năng. Như bài toán vị trí xe cứu thương<br /> hay bài toán lát<br /> ỨNG DỤNG TRONG BÀI TOÁN SO KHỚP<br /> CẤU TRÚC PHÂN TỬ<br /> Trong ngành công nghiệp dược phẩm và hoá<br /> chất nông nghiệp, bài toán xác định mối quan<br /> hệ cấu trúc giữa các cặp cấu trúc phân tử ba<br /> chiều là một bài toán quan trọng. Những cấu<br /> trúc phân tử ba chiều có thể được thể hiện<br /> bằng đồ thị. Ví dụ đối với cấu trúc Protein,<br /> các đỉnh của đồ thị được cho bởi các thành<br /> phần cấu trúc thứ cấp xoắn α và phiếm nếp<br /> gấp β , trong khi các cạnh được định nghĩa<br /> thông qua liên kết góc và khoảng cách giữa<br /> chúng [5]. Hơn nữa các đỉnh và cạnh đều<br /> được gán nhãn tương ứng với các kiểu nguyên<br /> tử và khoảng cách giữa các nguyên tử.<br /> Cho một cặp đồ thị đã được gán nhãn<br /> G1 = (V1 , E1 ) ; G2 = (V2 , E2 ) . Khi đó xây<br /> dựng đồ thị C , gọi là đồ thị tương ứng của<br /> hai đồ thị trên, như sau: Nếu hai đỉnh<br /> v1 ∈ V1 , v2 ∈ V2 có cùng nhãn thì cặp v1v2 là<br /> một đỉnh của C ; Hai đỉnh v1v2 và v1' v2' có<br /> liên kết cạnh nếu các cạnh<br /> <br /> (v , v ) ∈ E<br /> 2<br /> <br /> '<br /> 2<br /> <br /> 2<br /> <br /> (v , v ) ∈ E<br /> 1<br /> <br /> '<br /> 1<br /> <br /> 1<br /> <br /> và<br /> <br /> có nhãn giống nhau.<br /> 11<br /> <br /> Đàm Thanh Phương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> Với một cặp cấu trúc phân tử ba chiều, một<br /> đồ thị con chung lớn nhất trong hai đồ thị<br /> tương ứng của chúng liên hệ đến tập lớn nhất<br /> các nguyên tử có khoảng cách phù hợp. Vì<br /> vậy đồ thị con chung lớn nhất là một độ đo sự<br /> tương tự cấu trúc và cho thông tin quan trọng<br /> về hai phân tử.<br /> Theo cách xây dựng đồ thị C tương ứng từ<br /> hai đồ thị mô tả hai phân tử, ta nhận thấy đồ<br /> thị con giữa hai đồ thị G1 , G2 tương đương<br /> với clique trong đồ thị C . Vì vậy ta có thể<br /> tìm đồ thị con chung lớn nhất giữa hai đồ thị<br /> G1 , G2 thông qua việc giải bài toán clique lớn<br /> nhất trong đồ thị C tương ứng.<br /> Thách thức 3 (Thuật toán cho đồ thị tương<br /> ứng với mật độ thấp): Thiết kế thuật toán<br /> hiệu quả cho bài toán clique lớn nhất trên đồ<br /> thị tương ứng phát sinh từ bài toán so khớp<br /> cấu trúc phân tử hoá học ba chiều.<br /> Những thách thức tương tự cũng xảy ra khi<br /> tính toán clique lớn nhất cho bài toán ghép<br /> protein, trong đó người ta muốn tìm hiểu xem<br /> hai loại protein hình thành liên kết ổn định<br /> hay không, hoặc để so sánh các cấu trúc<br /> protein. [7]<br /> GIẢ THUYẾT KELLER<br /> Giả thuyết Keller liên quan đến giả thuyết<br /> Minkowski, trong đó nói rằng bài toán lưới lát<br /> n<br /> bởi các khối đơn vị, tồn tại hai khối cùng<br /> (n-1) mặt. Định lý Minkowski đã được chứng<br /> minh bởi Hajos năm 1950. Keller đề xuất<br /> tổng quát hoá định lý Minkowski bằng cách<br /> bỏ giả sử lưới. Trong thực tế, Prron đã chứng<br /> minh điều này là đúng với n ≤ 6 . Tuy nhiên<br /> với n ≥ 8 , giả sử lưới là cần thiết và đã được<br /> chứng minh bởi Lagarias. Giả thuyết Keller<br /> vẫn còn là vấn đề mở với n = 7 .<br /> Sau nhiều năm, các tranh luận về giả thuyết<br /> Keller vẫn chưa kết thúc. Qua đó, nhiều lớp<br /> đồ thị đối với bài toán clique lớn nhất cũng<br /> được phát sinh. Corradi và Szabo [6] đã xây<br /> dựng đồ thị gọi là đồ thị Keller Γ n với<br /> <br /> n∈<br /> <br /> +<br /> <br /> . Tập đỉnh của Γ n là các véc tơ với<br /> độ dài n , với giá trị 0, 1, 2 hoặc 3. Hai đỉnh<br /> bất kỳ có kết nối cạnh khi và chỉ khi trong n<br /> toạ độ, có đúng hai toạ độ khác nhau. Đồ thị<br /> Keller là đồ thị dày đặc với kích thước clique<br /> 12<br /> <br /> 102(02): 9 - 13<br /> <br /> bị chặn bởi 2n . Corradi và Szabo đã chứng<br /> minh rằng, tồn tại phản ví dụ về giả thuyết<br /> Keller khi và chỉ khi Γ n có clique kích thước<br /> bằng 2n .<br /> Với sự giúp đỡ của những kết quả này,<br /> Lagarias và Shor đã chỉ được phản ví dụ cho<br /> trường hợp số chiều n = 10 . Tương tự,<br /> Mackey đã xây dựng được clique với số chiều<br /> bằng 8, và chứng minh giả thuyết Keller<br /> không đúng khi n ≥ 8 . Tuy nhiên trong<br /> trường hợp n = 7 vẫn là vấn đề mở, và có<br /> thách thức sau:<br /> Thách thức 4 ( Bài toán mở [6]) Với đồ thị<br /> Keller Γ 7 , tìm clique lớn nhất có kích thước<br /> bằng 128 hoặc chứng minh không tồn tại<br /> clique như thế.<br /> KẾT LUẬN<br /> Chúng tôi đã hệ thống các ứng dụng dẫn tới<br /> các bài toán cliques, tựa clique, phân vùng<br /> clique trên các đồ thị lớn. Cấu trúc và tính<br /> chất của các đồ thị này có những điểm khác<br /> nhau. Nhưng nói chung kích thước và mật độ<br /> của chúng đều lớn. Điều này gây khó khăn<br /> cho việc thiết kế các thuật toán phù hợp với mỗi<br /> bài toán để có thể giải quyết chúng hiệu quả.<br /> TÀI LIỆU THAM KHẢO<br /> [1]. Hayes, B.: Graph Theory in Practice: PartI.<br /> American Scientist 88(1), 9(2000)<br /> [2]. Nanavati et all: Analyzing the Structure and<br /> Evolution of Massive Telecom Graphs. IEEE<br /> Trans actions on Knowledge and Data<br /> Engineering 20(5),703– 718(2008)<br /> [3]. Abello, Pardalos, Resende: On Maximum<br /> Clique Problems in Very Lagre Graphs. External<br /> Memory Algorithms .DIMACS Series, pp.119–<br /> 130, (1999)<br /> [4]. vanPul, et all: New lower bounds for constatn<br /> weight codes. IEEE Trans. Inform. Theory 35,<br /> 1324–1329 (1989)<br /> [5]. Mitchell et all : Use of techniques derived from<br /> Graph theory to compare secondary structure motifs<br /> in proteins. J.Mol.Biol.212, 151 (1990)<br /> [6]. Corradi and Szabo : A Combinatorial<br /> Approach for Keller’s Conjecture. Periodica<br /> Math. Hung. 21(2), 95–100 (1990)<br /> [7]. Butenko, S.,Wilhelm, W.: Clique-detection<br /> models in computational biochemistry and<br /> genomics. Euorpean Journal of<br /> Operational<br /> Research 173,1–17 (2006)<br /> <br /> Đàm Thanh Phương và Đtg<br /> <br /> Tạp chí KHOA HỌC & CÔNG NGHỆ<br /> <br /> 102(02): 9 - 13<br /> <br /> SUMMARY<br /> THE MAXIMUM CLIQUE PROBLEM – APPLICATIONS AND<br /> COMPUTATIONAL CHALLENGES<br /> Dam Thanh Phuong*, Ngo Manh Tuong, Khoa Thu Hoai<br /> College of Information and Communication Technology - TNU<br /> <br /> Maximum clique is a classical problem of graph theory and have many applications.<br /> Many problems in social, biology and finance networks resolved through finding cliques.<br /> Clique partitions and clique have also been used as a clustering or data classification<br /> tools. However, the actual problem is often modeled by a very large graph and requires<br /> large data storage memory for implementation of algorithms. In this paper, we discuss<br /> four applications and identify computational challenges which are both of theoretical and<br /> practical.<br /> Keywords: Cliques, quasi – cliques, clique partitions, independent set, maximum clique problem,<br /> maximum independent set.<br /> <br /> Ngày nhận bài:8/11/2012, ngày phản biện:19/12/2012, ngày duyệt đăng:26/3/2013<br /> *<br /> <br /> Tel: 0912 998749, Email: dtphuong@ictu.edu.vn<br /> <br /> 13<br /> <br />