Tính đạt được giữa 2 cấu hình chip trong Chip Firing Game trên đa đồ thị có hướng
  • Trang chủ
  • Tính đạt được giữa 2 cấu hình chip trong Chip Firing Game trên đa đồ thị có hướng

Tính đạt được giữa 2 cấu hình chip trong Chip Firing Game trên đa đồ thị có hướng

Thời gian: 09:30 đến 11:30 Ngày 24/11/2016

Địa điểm: phòng 201, nhà A5, Viện Toán học, 18 Hoàng Quốc Việt

Báo cáo viên: Nguyễn Duy Hoàng

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.