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

Li-Hsing Yen*, Guang Hong Sun

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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.

Original languageEnglish
Title of host publicationInternet and Distributed Computing Systems - 11th International Conference, IDCS 2018, Proceedings
EditorsAntonio Guerrieri, Jason J. Jung, Giancarlo Fortino, Jingtao Sun, Yang Xiang
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783030027377
StatePublished - 1 Jan 2018
Event11th International Conference on Internet and Distributed Computing Systems, IDCS 2018 - Tokyo, Japan
Duration: 11 Oct 201813 Oct 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11226 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Internet and Distributed Computing Systems, IDCS 2018


  • Distributed algorithm
  • Game theory
  • Independent dominating set
  • Self-stabilization


Dive into the research topics of 'Game-Theoretic Approach to Self-stabilizing Minimal Independent Dominating Sets'. Together they form a unique fingerprint.

Cite this