@inproceedings{e8a7cb4780f946e8b6f87e686145844f,
title = "Selfish Self-Stabilizing Approach to Maximal Independent Sets",
abstract = "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.",
keywords = "distributed algorithms, game theory, independent set, self-stabilization",
author = "Li-Hsing Yen and Huang, {Jean Yao}",
year = "2015",
month = dec,
day = "2",
doi = "10.1109/Trustcom.2015.607",
language = "English",
series = "Proceedings - 14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "9--16",
booktitle = "Proceedings - 13th IEEE International Symposium on Parallel and Distributed Processing with Applications, ISPA 2015",
address = "United States",
note = "14th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, TrustCom 2015 ; Conference date: 20-08-2015 Through 22-08-2015",
}