Speaker:

Zihui Liang (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• March 10, 2023 (Friday)

Venue:

518, Research Building 4

Abstract:

We introduce two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving M\”uller games. M\”uller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. We provide a charaterization theorem that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. We non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem.