Speaker:

Boting Yang (The University of Regina)

Time:

• 16:20-17:20 (Time in Beijing)
• May 30, 2024 (Thursday)

Venue:

518, Research Building 4

Abstract:

In this talk, we consider the one-visibility cops and robber game. The one-visibility cops and robber game is a variation of the classic cops and robber game, where one-visibility means that the information of the robber is known to all cops only when the distance between the robber and at least one cop is at most one. We give a lower bound on the one-visibility cop number of general trees. We propose strategies to clear trees according to their structures. We present a linear-time algorithm for computing the one-visibility cop number of trees. We also present an O(n log n)-time algorithm for computing the cop-win strategies of trees, where n is the number of vertices. 

Speaker Bio:

Boting Yang received the B.Sc. degree in mathematics from Fudan University, the M.Sc. and Ph.D. degrees in mathematics from Xi’an Jiaotong University, and the Ph.D. degree in computer science from Memorial University of Newfoundland. He is currently a professor at the University of Regina. His recent research focuses on Algorithmic Graph Theory, Computational Geometry, and Computational learning Theory.