### Abstract

A distributed system is self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in finite time. In 2007, Turau proposed the first linear-time self-stabilizing algorithm for the minimal dominating set (MDS) problem under an unfair distributed daemon [6]; this algorithm stabilizes in at most 9n moves, where n is the number of nodes. In 2008, Goddard et al. [2] proposed a 5n-move algorithm. In this paper, we present a 4n-move algorithm. We also prove that if an MDS-silent algorithm is preferred, then distance-1 knowledge is insufficient, where a self-stabilizing MDS algorithm is MDS-silent if it will not make any move when the starting configuration of the system is already an MDS.

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

Title of host publication | Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers |

Pages | 115-126 |

Number of pages | 12 |

DOIs | |

State | Published - 1 Dec 2013 |

Event | 24th International Workshop on Combinatorial Algorithms, IWOCA 2013 - Rouen, France Duration: 10 Jul 2013 → 12 Jul 2013 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8288 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 24th International Workshop on Combinatorial Algorithms, IWOCA 2013 |
---|---|

Country | France |

City | Rouen |

Period | 10/07/13 → 12/07/13 |

## Fingerprint Dive into the research topics of 'Linear-time self-stabilizing algorithms for minimal domination in graphs'. Together they form a unique fingerprint.

## Cite this

*Combinatorial Algorithms - 24th International Workshop, IWOCA 2013, Revised Selected Papers*(pp. 115-126). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8288 LNCS). https://doi.org/10.1007/978-3-642-45278-9_11