: 14h45, ngày 13/05/2022 (Thứ Sáu)
: P104 D3
: Seminar Toán rời rạc
: Dương
: K63 Tài năng Toán Tin
Tóm tắt báo cáo
It is well-known that finding minimum dominating set on graphs is a NP-hard problem. In this paper, we tried to answer the question of what cases make the problem become solvable in polynomial time. In particular, we will give concrete proof that a minimum dominating set can be found in polynomial time in class of graph (claw, P5)-free.