Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Seminars

 

Algorithms and Complexity (ACiD) Seminar: Semitotal Dominating Set

Presented by Andrea Munaro, Queen's University Belfast
26 November 2019 13:00 in E245

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size of a semitotal dominating set of a graph is squeezed between its domination number and its total domination number. In the talk, I will report on the systematic study on the computational complexity of Semitotal Dominating Set, the problem of finding, given a graph G, a minimum size semitotal dominating set of G. In particular, I will show that the problem is solvable in polynomial time for graphs of bounded mim-width and present several open problems. Joint work with Esther Galby and Bernard Ries

Contact algorithms.complexity@dur.ac.uk for more information