HOẠT ĐỘNG TRONG TUẦN

Thuật toán thời gian đa thức tính hạng của cấu hình trên đồ thị bánh xe
Người báo cáo: Phan Thị Hà Dương

Thời gian: 9h30 Thứ 5, 15/10/2015
Địa điểm: Phòng 201, Nhà A5, Viện Toán học, 18 Hoàng Quốc Việt, Cầu Giấy Hà Nội
Tóm tắt: Năm 2007, Baker và Norine đề xuất khái niệm hạng của divisor trên đồ thị và chứng minh định lý "Riemman Roch like Theorem" cho đồ thị. Kể từ đó bài toán tính hạng của các divisor đã thu hút được rất nhiều sự quan tâm. Trong kết quả năm 2015, Kiss and Tothmeresz đã chứng minh được bài toán tính hạng của các divisor trên đồ thị tổng quát là bài toán NP khó, kết quả này dựa trên kết quả về tính NP khó cho một bài toán về hệ CFG trên đồ thị Euler của Perot và Phạm.
Một số trường hợp đặc biệt của đồ thị đã được quan tâm, trong đó năm 2014 Cori và Le Borgne đã xây dựng thuật toán thời gian đa thức tính hạng của divisor cho đồ thị đầy đủ.
Trong semina này, chúng tôi trình bày thuật toán thời gian đa thức để tính hạng của divisor trên đồ thị bánh xe. Đây là kết quả hợp tác cùng R. Cori và T.T.H Trân.

Trở lại