Patrolling a Street Network is Strongly NP-Complete but in P for Tree Structures

Valentin E. Brimkov

We consider the following problem: Given a finite set of straight line segments in the plane, determine the positions of a minimal number of points on the segments, from which guar…