{"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":"2026-06-02T14:59:23","modified_gmt":"2026-06-02T18:59:23","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":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-07-21: Impact of Locality on Location Aware Unit Disk Graphs\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-2007\/\">Technical Report<\/a> TR-07-21<br>\nNovember 29, 2007<\/p>\n\n\n\n<h2 id=\"acl-specification\" class=\"wp-block-heading\">ACL Specification<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<p class=\"tr_t3\">Andreas Wiese &amp; Evangelos Kranakis<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<p>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<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-07-21.pdf\">TR-07-21.pdf<\/a><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-07-21 November 29, 2007 ACL Specification Andreas Wiese &amp; 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 [&hellip;]<\/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-13227","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13227","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=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"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13227"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}