### Abstract

Dominating set is a subset of nodes called dominators in a graph such that every non-dominator nodes (called dominatee) is adjacent to at least one dominator. This paper considers a more general multi-dominating problem where each node i, dominator or dominatee, is required to have at least k
_{i}
neighboring dominators, and different node can have different k
_{i}
value. We first propose a game design toward this problem. This game is self-stabilizing (i.e., it always ends up with a legitimate state regardless of its initial configuration). The obtained result is guaranteed minimal (i.e., it contains no proper subset that is also a multi-dominating set) and Pareto optimal (we cannot increase the payoff of some player without sacrificing the payoff of any other). We then point out challenges when turning the design into a distributed algorithm using guarded commands. We present an algorithm that is proved weakly stabilizing. Simulation results show that the proposed game and algorithm produce smaller dominating sets, k-dominating sets, and multi-dominating sets in various network topologies when compared with prior approaches.

Original language | English |
---|---|

Article number | 6714459 |

Pages (from-to) | 3201-3210 |

Number of pages | 10 |

Journal | IEEE Transactions on Parallel and Distributed Systems |

Volume | 25 |

Issue number | 12 |

DOIs | |

State | Published - 1 Dec 2014 |

### Keywords

- Distributed algorithm
- Dominating set
- Game theory
- Self-stabilization

## Fingerprint Dive into the research topics of 'Game-theoretic approach to self-stabilizing distributed formation of minimal multi-dominating sets'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Parallel and Distributed Systems*,

*25*(12), 3201-3210. [6714459]. https://doi.org/10.1109/TPDS.2013.2297100