networks (WSNs), especially to cope against compromised nodes. A node v can monitor an
edge e if both end-nodes of e are neighbors of v; ie, e together with v forms a triangle in the
graph. Moreover, some edges need more than one monitor. Finding a set of monitoring
nodes satisfying all monitoring constraints is called the edge-monitoring problem. The
minimum edge-monitoring problem is long known to be NP-complete. In this paper, we …