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

Abstract

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
Pages173-184
Number of pages12
ISBN (Print)9783030027377
DOIs
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

Conference

Conference11th International Conference on Internet and Distributed Computing Systems, IDCS 2018
CountryJapan
CityTokyo
Period11/10/1813/10/18

Keywords

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

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

Cite this