• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Technique et science informatiques >Un algorithme autostabilisant pour le problème du K-partitionnement sur graphe pondéré
【24h】

Un algorithme autostabilisant pour le problème du K-partitionnement sur graphe pondéré

机译：加权图上K划分问题的一种自稳定算法。

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

摘要

Les réseaux mobiles ad hoc ainsi que les plates-formes de grille sont des environnements distribués et sujets à de nombreuses erreurs. Les coûts de communication au sein de ces infrastructures peuvent être améliorés, ou tout au moins bornés par l'utilisation d'un k-regroupement. Un k-regroupement d'un graphe est une partition de nœuds en ensembles disjoints, nommés grappes ou clusters, dans lesquels chaque nœud est à une distance au plus k d'un nœud élu au sein de la grappe, appelé clusterhead. Nous présentons un algorithme asynchrone, distribué et autostabilisant pour construire un k-regroupement d'un réseau de nœuds ayant des identifiants uniques, et connectés par des arêtes pondérées. L'algorithme se base sur des comparaisons entre les identifiants, il s'exécute en O(nk), et requiert O(log n + log k) d'espace mémoire par processus, où n est la taille du réseau. A notre connaissance, c 'est la première solution distribuée au problème du k-regroupement sur des graphes pondérés.%Mobile ad hoc networks as well as grid platforms are distributed, changing and error prone environments. Communication costs within such infrastructure can be improved, or at least bounded, by using k-clustering. A k-clustering of a graph, is a partition of the nodes into disjoint sets, called clusters, in which every node is at a distance at most k from a designated node in its cluster, called the clusterhead. A self-stabilizing asynchronous distributed algorithm is given for constructing a k-clustering of a connected network of processes with unique IDs and weighted edges. The algorithm is comparison-based, takes O(nk) time, and uses O(log n + log k) space per process, where n is the size of the network. To the best of our knowledge, this is the first distributed solution to the k-clustering problem on weighted graphs.
机译：Ad hoc移动网络和网格平台是分布式环境，容易出错。这些基础结构中的通信成本可以提高，或者至少可以通过使用k组来限制。图的k-分组是将节点划分为不相交的集合（称为簇或簇），其中每个节点距簇内选举的节点（称为簇头）最多k。我们提出一种异步，分布式和自稳定算法，以构建具有唯一标识符并由加权边连接的节点网络的k组。该算法基于标识符之间的比较，它以O（nk）运行，并且每个进程需要O（log n + log k）的存储空间，其中n是网络的大小。据我们所知，这是加权图上k分组问题的第一个分布式解决方案。％移动自组织网络以及网格平台是分布式，变化和易于出错的环境。通过使用k聚类，可以改善或至少限制这种基础结构内的通信成本。图的k聚类是将节点划分为不相交的集合（称为簇），其中每个节点与其簇中指定节点（称为簇头）的距离最大为k。给出了一种自稳定的异步分布式算法，用于构造具有唯一ID和加权边的进程连接网络的k聚类。该算法基于比较，花费O（nk）时间，每个进程使用O（log n + log k）空间，其中n是网络的大小。据我们所知，这是加权图上k聚类问题的第一个分布式解决方案。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号