کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6423760 | 1632577 | 2016 | 6 صفحه PDF | دانلود رایگان |
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.
Journal: Electronic Notes in Discrete Mathematics - Volume 54, October 2016, Pages 331-336