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

Research & business

Research lectures, seminars and events

The events listed in this area are research seminars, workshops and lectures hosted by Durham University departments and research institutes. If you are not a member of the University, but  wish to enquire about attending one of the events please contact the organiser or host department.


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 for more information