Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423760 | Electronic Notes in Discrete Mathematics | 2016 | 6 Pages |
Edge monitoring is a simple and effective mechanism for the security of wireless sensor networks. The idea is to award specific roles (monitors) to some sensor nodes of the network. A node v monitors an edge e if both extremities together with v form a triangle in the graph. Given an edge colored graph G=(V,E,c), the color c(e) is a positive integer representing the number of monitors needed by the edge e. The problem is to seek a minimum cardinality subset of monitors S such that every edge e in the graph is monitored by at least c(e) vertices in S. If vertices of G are weighted, the objective then is to minimize the total weight of vertices of S and the problem is called weighted edge monitoring problem. In this paper, we present a polynomial-time algorithm for finding an edge monitoring set of minimum weight in interval graphs.