Hoạt động trong tuần

Tính đạt được giữa 2 cấu hình chip trong Chip Firing Game trên đa đồ thị có hướng (part 2)
Người báo cáo: Nguyễn Duy Hoàng
Thời gian: 9h30, Thứ 5, ngày 15 tháng 12 năm 2016
Địa điểm: Phòng 201, Nhà A5, Viện Toán học
Tóm tắt: Trong bài báo cáo sẽ giới thiệu về bài toán tính đạt được của 2 cấu hình, ý nghĩa của nó và trình bày một số kết quả nghiên cứu tiêu biểu về bài toán bao gồm:
  1. Chip-firing games on directed graphs của 2 tác giả Anders Bj¨orner và  L´aszl´o Lov´asz. Trong bài báo các tác giả đã đề xuất một thuật toán đơn giản để giải quyết bài toán.
  2. On the complexity of the chip-firing reachability problem của nhóm tác giả B´alint Hujter, Viktor Kiss, and Lilla T´othm´er´esz. Các tả giả đã chỉ ra bài toán thuộc lớp Co-NP, và đưa thuật toán có thời gian đa thức trong một số trường hợp đặc biệt của bài toán..

Trở lại