On the Dominating Set Problem

Thời gian: 09:30 đến 11:00 Ngày 16/05/2019

Địa điểm: C2-714, VIASM

Báo cáo viên: Lê Chí Ngọc, ĐH Bách Khoa Hà Nội

Tóm tắt:

Given a graph $G = (V,E)$, a vertex subset $D \subset V$ is called a dominating set if every vertex not lying in $D$ adjacent to some vertex in $D$. The problem of asking a dominating set of minimum cardinality was shown to be NP-hard in general. In this research, we consider some variances, some extensions of the problem, the NP-hardness of them. We also propose a new approach to tackle the problems. From that, some graph classes, under which we have polynomial time solutions for these problems are found.