Sofwareprojektpraktikum: Cops'n'Robber – Search Games on Graphs, Decompositions and Connectivity

 

Sofwareprojektpraktikum: Cops'n'Robber

The "Cops'n'Robber" game is an abstract game where players move on the nodes of a graph and a fixed number of "cops" try to catch a "robber".

Search games on graphs, of which the "Cops'n'Robber" game is the most important, allow us to measure the global coherence of graphs and thus ultimately the robustness of network topologies. Closely related is the decomposability of graphs into small pieces, on which in turn many dynamic programming algorithms are based.

Task

In this lab, efficient strategies for the players in the Cops'n'Robber game are to be implemented. At the end of the lab, the strategies of each group will compete against each other in a competition.

Area and requirements

The content of the internship is in the area of graph algorithms. A good knowledge of data structures and algorithms is required. The implementation will be done in Python, possibly with C++ components. Knowledge of these languages is also expected.