报告题目: Fast Searching on Graphs.
报告人: Boting Yang
Given a graph, suppose that a fugitive hides on vertices or along edges of the graph. The fast searching problem is to find the minimum number of searchers required to capture the fugitive satisfying the constraint that every edge is traversed exactly once and searchers are not allowed to jump. In this talk, we present results on the fast search number of the Cartesian product of graphs, including hypercubes and toroidal grids. We give lower bounds and upper bounds on the fast search number of complete $k$-partite graphs. We also present results on the fast search number of other classes of graphs, such as Halin graphs, cubic graphs, bipartite graphs and split graphs.
报告人简介: Boting Yang, Professor ofDepartment of Computer Science，University of Regina,Regina Saskatchewan Canada.