{"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":"2021-12-07T20:57:10","modified_gmt":"2021-12-08T01:57:10","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":"

Carleton University
\nTechnical Report<\/a> TR-07-17
\nOctober 3, 2007<\/p>\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

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":49,"featured_media":0,"parent":12385,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-07-17 October 3, 2007 Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"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\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"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\/\",\"url\":\"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\/\",\"name\":\"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T01:56:56+00:00\",\"dateModified\":\"2021-12-08T01:57:10+00:00\",\"description\":\"Carleton University Technical Report TR-07-17 October 3, 2007 Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph\",\"breadcrumb\":{\"@id\":\"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\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"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\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"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\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 2007\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph - School of Computer Science","description":"Carleton University Technical Report TR-07-17 October 3, 2007 Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"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\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"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\/","url":"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\/","name":"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T01:56:56+00:00","dateModified":"2021-12-08T01:57:10+00:00","description":"Carleton University Technical Report TR-07-17 October 3, 2007 Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph","breadcrumb":{"@id":"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\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["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\/"]}]},{"@type":"BreadcrumbList","@id":"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\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 2007","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/"},{"@type":"ListItem","position":5,"name":"TR-07-17: Local PTAS for Dominating and Connected Dominating Set in Location Aware Unit Disk Graph"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13219"}],"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\/49"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}