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:
- 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.
- 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..
|
