• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >Game-Theoretic Approach to Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Sets
【24h】

Game-Theoretic Approach to Self-Stabilizing Distributed Formation of Minimal Multi-Dominating Sets

机译：最小多支配集自稳定分布形式的博弈论方法

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

摘要

Dominating set is a subset of nodes called dominators in a graph such that every non-dominator nodes (called dominatee) is adjacent to at least one dominator. This paper considers a more general multi-dominating problem where each node , dominator or dominatee, is required to have at least neighboring dominators, and different node can have different value. We first propose a game design toward this problem. This game is self-stabilizing (i.e., it always ends up with a legitimate state regardless of its initial configuration). The obtained result is guaranteed minimal (i.e., it contains no proper subset that is also a multi-dominating set) and Pareto optimal (we cannot increase the payoff of some player without sacrificing the payoff of any other). We then point out challenges when turning the design into a distributed algorithm using guarded commands. We present an algorithm that is proved weakly stabilizing. Simulation results show that the proposed game and algorithm produce smaller dominating sets, -dominating sets, and multi-dominating sets in various network topologies when compared with prior approaches.
机译：支配集是图中一个称为支配者的节点的子集，这样每个非支配者节点（称为支配者）都与至少一个支配者相邻。本文考虑了一个更普遍的多支配问题，其中每个节点（支配者或支配者）都必须至少具有相邻的支配者，并且不同的节点可以具有不同的值。我们首先提出针对此问题的游戏设计。该游戏具有自我稳定性（即，无论其初始配置如何，它始终以合法状态结束）。获得的结果保证为最小（即，它不包含也是多支配集的适当子集）和帕累托最优（我们不能在不牺牲任何其他参与者的收益的情况下增加某些玩家的收益）。然后，我们指出了使用受保护的命令将设计转变为分布式算法时的挑战。我们提出了一种被证明弱稳定的算法。仿真结果表明，与现有方法相比，所提出的游戏和算法在各种网络拓扑中产生较小的控制集，控制集和多控制集。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号