Hoppa direkt till innehållet

Studenter som inte bytt lösenord sedan 7 maj kan inte logga in på studentwebben. Detta p.g.a. skyddsåtgärder vid cyberattacken den 2 maj. Läs hur du byter lösenord.

Huvudmenyn dold.

Maker-Breaker domination game

Tid Torsdag 21 oktober, 2021 kl. 14:15 - 15:15
Plats Zoom

The Maker-Breaker domination game is a two player game played on a graph. The two players, Dominator and Staller, alternatively select vertices of the graph. If at some point, the vertices selected by Dominator form a dominating set, he wins the game. If however Staller can keep Dominator from ever dominating the graph, she wins the game.

As in every two player game with perfect information, one of the two players is bound to have a winning strategy. The goal of this talk will be to study two problems: the first one is to determine which player has a winning strategy and the other one is to know the number of moves Dominator needs to play to win the game, assuming he has a winning strategy. We give complexity results for both of these problems.

Due to the ongoing covid-19 epidemic, seminars are via Zoom. To receive the Zoom link, please contact the seminar organiser: Maryam Sharifzadeh

Evenemangstyp: Seminarium
Maryam Sharifzadeh
Läs om Maryam Sharifzadeh