...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Analysing local algorithms in location-aware quasi-unit-disk graphs
【24h】

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

机译：分析位置感知的准单位磁盘图中的局部算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：具有局部视野r的局部算法是在r同步通信回合中运行的分布式算法。在此，r是不依赖于网络大小的常数。结果，局部算法中节点的输出仅取决于该节点的r个跳内的输入。对于单元磁盘图（UDG）上组合问题的一类局部算法，我们在局部范围上给出了严格的界限。我们的大多数界限是由于对现有方法的精确分析，而其他界限则是通过建议新算法获得的。我们考虑的算法基于以平面矩形拼贴为指导的网络分解。该算法适用于匹配，独立集，图形着色，顶点覆盖和支配集。我们还研究了准UDG的本地算法，这是UDG的一种流行概括，旨在对网络节点之间的通信进行更真实的建模。分析准UDG上的局部算法，可以假定节点仅大致了解其坐标，直至累加误差为止。尽管存在本地化错误，准UDG上问题的解决方案的质量仍与具有完善位置意识的UDG的情况相同。我们分析了从UDG过渡到准UDG带来的当地视野的增长。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号