{"id":13219,"date":"2021-12-07T20:56:56","date_gmt":"2021-12-08T01:56:56","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13219"},"modified":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","slug":"tr-07-17-local-ptas-for-dominating-and-connected-dominating-set-in-location-aware-unit-disk-graph","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-17-local-ptas-for-dominating-and-connected-dominating-set-in-location-aware-unit-disk-graph\/","title":{"rendered":"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph\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-07-17
\nOctober 3, 2007<\/p>\n\n\n\n

Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
\n

Andreas Wiese & Evangelos Kranakis<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n

\n

Abstract<\/h3>\n

We present local $1+\\epsilon$ approximation algorithms for the minimum dominating and the connected dominating set problems in location aware Unit Disk Graphs (UDGs). Our algorithms are local in the sense that the status of a vertex $v$ (i.e. whether or not $v$ is part of the set to be computed) depends only on the vertices which are a constant number of edges (hops) away from $v$. This constant is independent of the size of the network. In our graph model we assume that each vertex knows its geographic coordinates in the plane (location aware nodes). Our algorithms give the best approximation ratios known for this setting. Moreover, the processing time that each vertex needs to determine whether or not it is part of the computed set is bounded by a polynomial in the number of vertices which are a constant number of hops away from it.<\/p>\n

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

Carleton University Technical Report TR-07-17 October 3, 2007 Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph Andreas Wiese & Evangelos Kranakis Abstract We present local $1+\\epsilon$ approximation algorithms for the minimum dominating and the connected dominating set problems in location aware Unit Disk Graphs (UDGs). Our algorithms are local […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12385,"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-13219","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13219","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=13219"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13219\/revisions"}],"predecessor-version":[{"id":13220,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13219\/revisions\/13220"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12385"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13219"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13219"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}