A time-constrained variation of the Watchman's Walk problem.
Danny Dyer, Rebecca Milley · Australas. J Comb. · 2012
Given a graph and a single watchman, the objective of the Watchman’s Walk Problem is to find a closed dominating walk of minimum length which the watchman can traverse to efficiently guard the graph. When multiple guards are available, one natural variation is to assume fixed time constraints on the monitoring of vertices and attempt to minimize the number of guards required. We find upper bounds on the number of guards required to monitor trees when no vertex is unobserved for more than t units of time.