{"id":13227,"date":"2021-12-07T21:03:18","date_gmt":"2021-12-08T02:03:18","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13227"},"modified":"2021-12-07T21:03:36","modified_gmt":"2021-12-08T02:03:36","slug":"tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/","title":{"rendered":"TR-07-21: Impact of Locality on Location Aware Unit Disk Graphs"},"content":{"rendered":"

Carleton University
\nTechnical Report<\/a> TR-07-21
\nNovember 29, 2007<\/p>\n

ACL Specification<\/h2>\n
\n
\n
\n
\n
\n
\n
\n
\n

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

\n

Abstract<\/h3>\n

A network algorithm is local if the status of a vertex depends only on the vertices which are at most a constant (independent of the size of the network) number of hops away from it. Due to their importance for studies on wireless networks, recent years have seen a surge of activity on the design of local algorithms for the solution of a variety of network tasks. Nevertheless, there are only a few lower bounds known for approximation factors of local algorithms and none for local algorithms in the setting of location aware nodes. In this paper we investigate the impact of very low locality (i.e., number of hops) on the design of algorithms in location aware UDGs. We prove the first ever lower bounds for local algorithms of a given locality for minimum dominating and connected dominating set, maximum independent set and minimum vertex cover in the location aware setting. Then we study the prospects of algorithms with very low localities. Despite of this restriction we propose local constant ratio approximation algorithms for solving these problems in Unit Disk Graphs. We compare the bounds obtained by designing even tighter upper bounds on Unit Line Graphs (a special class of UDGs whereby all vertices lie on the same line) and contrast them by proving lower bounds for arbitrary locality on these graphs.<\/p>\n

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

Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese & Evangelos Kranakis Abstract A network algorithm is local if the status of a vertex depends only on the vertices which are at most a constant (independent of the size of the network) number of hops away from it. Due to their importance […]<\/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-21: Impact of Locality on Location Aware Unit Disk Graphs - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese & Evangelos Kranakis Abstract A network algorithm is\" \/>\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-21-impact-of-locality-on-location-aware-unit-disk-graphs\/\" \/>\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-21-impact-of-locality-on-location-aware-unit-disk-graphs\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/\",\"name\":\"TR-07-21: Impact of Locality on Location Aware Unit Disk Graphs - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-12-08T02:03:18+00:00\",\"dateModified\":\"2021-12-08T02:03:36+00:00\",\"description\":\"Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese & Evangelos Kranakis Abstract A network algorithm is\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/#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-21: Impact of Locality on Location Aware Unit Disk Graphs\"}]},{\"@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-21: Impact of Locality on Location Aware Unit Disk Graphs - School of Computer Science","description":"Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese & Evangelos Kranakis Abstract A network algorithm is","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-21-impact-of-locality-on-location-aware-unit-disk-graphs\/","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-21-impact-of-locality-on-location-aware-unit-disk-graphs\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/","name":"TR-07-21: Impact of Locality on Location Aware Unit Disk Graphs - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-12-08T02:03:18+00:00","dateModified":"2021-12-08T02:03:36+00:00","description":"Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese & Evangelos Kranakis Abstract A network algorithm is","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/tr-07-21-impact-of-locality-on-location-aware-unit-disk-graphs\/#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-21: Impact of Locality on Location Aware Unit Disk Graphs"}]},{"@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\/13227"}],"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=13227"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13227\/revisions"}],"predecessor-version":[{"id":13229,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13227\/revisions\/13229"}],"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=13227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}