{"id":13177,"date":"2021-12-07T20:21:02","date_gmt":"2021-12-08T01:21:02","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13177"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-06-11-incremental-construction-of-k-dominating-sets-in-wireless-sensor","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2006\/tr-06-11-incremental-construction-of-k-dominating-sets-in-wireless-sensor\/","title":{"rendered":"TR-06-11: Incremental Construction of k-Dominating Sets in Wireless Sensor"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-06-11: Incremental Construction of k-Dominating Sets in Wireless Sensor\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-06-11
\nDecember 18, 2006<\/p>\n\n\n\n

Incremental Construction of k-Dominating Sets in Wireless Sensor<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least k neighbors in S. We present a new incremental local algorithm to construct a k-dominating set. The algorithm constructs a monotone family of dominating sets D1\u2264 D2…\u2264 Di…\u2264 Dk such that each Di is an i-dominating set. For unit disk graphs, the size of each of the resulting i-dominating sets is at most six times the optimal.<\/p>\n

TR-06-11.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-06-11 December 18, 2006 Incremental Construction of k-Dominating Sets in Wireless Sensor Mathieu Couture, Michel Barbeau, Prosenjit Bose, Evangelos Kranakis Abstract Given a graph G, a k-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12352,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13177","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13177","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13177"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13177\/revisions"}],"predecessor-version":[{"id":13178,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13177\/revisions\/13178"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12352"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13177"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13177"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}