Người báo cáo: Phan Thị Hà Dương
Thời gian: 9h30, ngày thứ 5, ngày 26 tháng 10 năm 2017
Địa điểm: Phòng 611 - 612, nhà A6, Viện Toán học, 18 Hoàng Quốc Việt
Tóm tắt: Các đồ thị lớn biểu diễn các mạng phức tạp có tính chất chung là co cụm (cluster): đồ thị gồm một số đồ thị con có mật độ cạnh rất cao và giữa các đồ thị con thì có rất ít cạnh. Chính vì vậy nhiều công trình đã nghiên cứu bài toán clique editing hay cluster editing để xấp xỉ đồ thị ban đầu bằng các cụm. Cụ thể, bài toán clieque editing được phát biểu: Cho trước một đồ thị G và một số k, hỏi có thể thêm bớt tối đa k cạnh vào G để đồ thị mới nhận được gồm một clique (đồ thị đầy đủ) và các đỉnh độc lập hay không ? Tổng quát, thì đồ thị nhận được là hợp rời của một số clique và các đỉnh độc lập.
Bài toán này là bài toán NP- đầy đủ (theo n, số đỉnh của đồ thị).
Một hướng nghiên cứu các bài toán NP-khó là nghiên cứu thuật toán có độ phức tạp tham số (parameterized complexity). Trong đó lớp bài toán được quan tâm là lớp bài toán giải được với tham số cố định FPT (fixed-parameter tractable). Một bài toán FPT là bài toán có thuật giải trong thời gian f(k)* p(n) trong đó p(n) là đa thức theo n, còn f(k) là một hàm tuỳ ý (có thể là hàm mũ) theo tham số k (số cạnh cần thêm, bớt).
Trong Semina này, chúng tôi sẽ trình bày các khái niệm nói trên. Trình bày kết quả của một số tác giả về thuật toán FPT cho bài toán clique editing. Cuối cùng chúng tôi trình bày kết quả mới của mình: thuật toán FPT cho bài toán clique editing và cluster editing trên đồ thị có nhiều màu. Bài toán này được úng dụng trong hướng nghiên cứu mới về mạng các liên kết Internet có yếu tố thời gian ((Stream Graphs and Link Streams). Đây là kết quả hợp tác với M. Latapy, C. Magnien và B. M. Bui Xuan (Paris 6). |
