Connection Games in Graphs 🗓 🗺
Prof. Ulrich Pferschy dell’Università di Graz
When and Where
Mercoledì 28 settembre 2016 alle 11.30 presso la sala riunioni del Dipartimento di Ingegneria dell’Università Roma Tre,
We consider games of two agents/players on a graph: The players start in two different vertices and form paths until a connection is established, i.e. the two paths meet. The players move along the edges of a graph and take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge.
We want to determine the optimal path, in the sense that each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution can be determined by backward induction in the game tree. We will show complexity results and polynomiallly solvable cases on different classes of graphs.
Per ulteriori informazioni rivolgersi a G. Nicosia (email@example.com, tel. 06 57333455).