The Minimum Dominating Set Problem on Some Families of Graphs

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


Đánh giá bài viết


Xem thêm