On the Dominating Set Problem

Time: 09:30 to  11:00 Ngày 16/05/2019

Venue/Location: C2-714, VIASM

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

Content:

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.