Connectivity in the presence of an opponent
- Speaker
- Zihui Liang
- Affiliation
- University of Electronic Science and Technology of China
- Date
- Time
- – Asia/Shanghai
- 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üller games. Müller 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.