Analysing local algorithms in location-aware quasi-unit-disk graphs

Show simple item record

dc.contributor University of Helsinki, Helsinki Institute for Information Technology en
dc.contributor University of Helsinki, Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan) en
dc.contributor University of Helsinki, Helsinki Institute for Information Technology en Hassinen, Marja Kaasinen, Joel Kranakis, Evangelos Polishchuk, Valentin Suomela, Jukka Wiese, Andreas 2011-10-12T08:50:01Z 2011-10-12T08:50:01Z 2011
dc.identifier.citation Hassinen , M , Kaasinen , J , Kranakis , E , Polishchuk , V , Suomela , J & Wiese , A 2011 , ' Analysing local algorithms in location-aware quasi-unit-disk graphs ' , Discrete Applied Mathematics , vol. 159 , no. 15 , pp. 1566–1580 . en
dc.identifier.issn 0166-218X
dc.identifier.other PURE: 19027746
dc.identifier.other PURE UUID: 654576f2-8b76-4c1c-a647-f63591d83b06
dc.identifier.other WOS: 000294746100009
dc.identifier.other Scopus: 79960901936
dc.description.abstract A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs. en
dc.language.iso eng
dc.relation.ispartof Discrete Applied Mathematics
dc.rights en
dc.subject 113 Computer and information sciences en
dc.subject 111 Mathematics en
dc.title Analysing local algorithms in location-aware quasi-unit-disk graphs en
dc.type Article
dc.description.version Peer reviewed
dc.type.uri info:eu-repo/semantics/other
dc.type.uri info:eu-repo/semantics/acceptedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
hassinen_2011_qudg.pdf 392.0Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record