Seminar: An Introduction to Fast-Mixed Searching and Related Problems

Mon., Mar. 28, 2016 1:30 p.m.

Location: CL 431

Title: An Introduction to Fast-Mixed Searching and Related Problems

Speaker: Yuan Xue
Date: March 28 (M)
Time: 1:30pm - 2:20pm
Room: CL 431

Abstract: Assume that we want to eliminate a computer virus in a network. We can model this network as a graph, where nodes in the network correspond to vertices and cables between nodes correspond to edges. In order to eliminate the virus and secure the whole network, we will launch a group of searchers into the network. Here comes an optimization question: what is the fewest number of searchers required to perform this task?

Graph searching, also called Cops and Robbers games, has become a hot topic dealing with this kind of optimization problems. In this presentation, we give an introduction to the fast-mixed search problem, and establish relations between the fast-mixed search problem and other graph search problems.