Hoppa direkt till innehållet
printicon
Huvudmenyn dold.

Maker-Breaker domination game

tor
21
okt
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
Personalbild Valentin Gledel
Talare
Valentin Gledel
Postdoktor
Läs om Valentin Gledel
Kontaktperson
Maryam Sharifzadeh
Läs om Maryam Sharifzadeh