TR-07-21: Impact of Locality on Location Aware Unit Disk Graphs

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 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.

TR-07-21.pdf