Searching and sweeping graphs: A brief survey

Abstract

This papers surveys some of the work done on trying to capture an intruder in a graph. If the intruder may be located only at vertices, the term searching is employed. If the intruder may be located at vertices or along edges, the term sweeping is employed. There are a wide variety of applications for searching and sweeping. Old results, new results and active research directions are discussed. 1