Game-Theoretic Approach to Self-stabilizing Minimal Independent Dominating Sets

Li-Hsing Yen*, Guang Hong Sun

*Corresponding author for this work

研究成果: Conference contribution同行評審

摘要

An independent dominating set (IDS) is a set of vertices in a graph that ensures both independence and domination. The former property asserts that no vertices in the set are adjacent to each other while the latter demands that every vertex not in the set is adjacent to at least one vertex in the IDS. We extended two prior game designs, one for independent set and the other for dominating set, to three IDS game designs where players independently determine whether they should be in or out of the set based on their own interests. Regardless of the game play sequence, the result is a minimal IDS (i.e., no proper subset of the result is also an IDS). We turned the designs into three self-stabilizing distributed algorithms that always end up with an IDS regardless of the initial configurations. Simulation results show that all the game designs produce relatively small IDSs with reasonable convergence rate in representative network topologies.

原文English
主出版物標題Internet and Distributed Computing Systems - 11th International Conference, IDCS 2018, Proceedings
編輯Antonio Guerrieri, Jason J. Jung, Giancarlo Fortino, Jingtao Sun, Yang Xiang
發行者Springer Verlag
頁面173-184
頁數12
ISBN(列印)9783030027377
DOIs
出版狀態Published - 1 一月 2018
事件11th International Conference on Internet and Distributed Computing Systems, IDCS 2018 - Tokyo, Japan
持續時間: 11 十月 201813 十月 2018

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
11226 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference11th International Conference on Internet and Distributed Computing Systems, IDCS 2018
國家Japan
城市Tokyo
期間11/10/1813/10/18

指紋 深入研究「Game-Theoretic Approach to Self-stabilizing Minimal Independent Dominating Sets」主題。共同形成了獨特的指紋。

引用此