Selfish Self-Stabilizing Approach to Maximal Independent Sets

Li-Hsing Yen, Jean Yao Huang

研究成果: Conference contribution同行評審

摘要

Given an undirected graph G = (V, E), a subset S of V is an independent set if no two nodes in S are adjacent to each other. S is a maximal independent set (MIS) if no proper superset of S is also an independent set. We model the problem of finding an MIS in a distributed system as a noncooperative graphical game and propose an algorithmic mechanism design for the problem. We show Nash equilibrium, correctness, and Pareto optimality of the design and then turn the design into a self-stabilizing algorithm running under a synchronous daemon. The convergence property and time complexity of the algorithm is shown. Simulation results indicate that the proposed protocol performs better than previous work in terms of MIS size under various representative types of network topologies.

原文English
主出版物標題Proceedings - 13th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2015
發行者Institute of Electrical and Electronics Engineers Inc.
頁面9-16
頁數8
ISBN(電子)9781467379519
DOIs
出版狀態Published - 2 十二月 2015
事件14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015 - Helsinki, Finland
持續時間: 20 八月 201522 八月 2015

出版系列

名字Proceedings - 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015
3

Conference

Conference14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015
國家Finland
城市Helsinki
期間20/08/1522/08/15

指紋 深入研究「Selfish Self-Stabilizing Approach to Maximal Independent Sets」主題。共同形成了獨特的指紋。

引用此