Graph Search Techniques
Boting Yang · Wiley Encyclopedia of Operations Research and Management Science · 2011
Abstract Given a graph, suppose that there is a robber hiding on vertices or along edges. A graph searching problem is to find the minimum number of searchers required to capture the robber. In this article, we describe the main characteristics of graph searching problems. For undirected graphs, we consider the edge search, node search, mixed search, visible‐robber game, and inert‐robber game. For digraphs, we consider directed search, strong search, weak search, strong direct visible‐robber game, directed visible‐robber game, and directed inert‐robber game. We also deal with cops‐and‐robber games in which cops and the robber take turns to move. Most searching problems correspond to width parameters in graph theory. We describe the relationships between models and width parameters. We only survey the basic models, giving references to other variants.