Search

Your search keyword '"minimal dominating set"' showing total 4 results
Start Over Descriptor "minimal dominating set" Topic self-stabilization
4 results on '"minimal dominating set"'

1. A Self-Stabilizing Distributed Algorithm for the Generalized Dominating Set Problem With Safe Convergence.

Author

Kobayashi, Hisaki, Sudo, Yuichi, Kakugawa, Hirotsugu, and Masuzawa, Toshimitsu

Subjects
*DOMINATING set, *DISTRIBUTED algorithms, *ALGORITHMS
Abstract

A self-stabilizing distributed algorithm is guaranteed eventually to reach and stay at a legitimate configuration regardless of the initial configuration of a distributed system. In this paper, we propose the generalized dominating set problem, which is a generalization of the dominating set and |$k$| -redundant dominating set problems. In the generalized dominating set we propose in this paper, each node |$P_{i}$| is given its set of domination wish sets, and a generalized dominating set is a set of nodes such that each node is contained in the set or has a wish set in which all its members are in the set. We propose a self-stabilizing distributed algorithm for finding a minimal generalized dominating set in an arbitrary network under the unfair distributed daemon. The proposed algorithm converges in |$O(n^{3}m)$| steps and |$O(n)$| rounds, where |$n$| (resp. |$m$|⁠) is the number of nodes (resp. edges). Furthermore, it has the safe convergence property with safe convergence time in |$O(1)$| rounds. The space complexity of the proposed algorithm is |$O(\Delta \log n)$| bits per node, where |$\Delta $| is the maximum degree of nodes. [ABSTRACT FROM AUTHOR]

Published
2023
Full Text
View/download PDF

2. Brief Announcement: Fully Lattice Linear Algorithms

Author

Gupta, Arya Tanmay, Kulkarni, Sandeep S., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Devismes, Stéphane, editor, Petit, Franck, editor, Altisen, Karine, editor, Di Luna, Giuseppe Antonio, editor, and Fernandez Anta, Antonio, editor

Published
2022
Full Text
View/download PDF

3. Self-Stabilizing Algorithm for Minimal Dominating Set with Safe Convergence in an Arbitrary Graph.

Author

Ding, Yihua, Wang, James Z., and Srimani, Pradip K.

Subjects
*GRAPH theory, *ALGORITHMS, *STOCHASTIC convergence, *ARBITRARY constants, *SET theory
Abstract

In a graph or a network , a set is a dominating set if each node in is adjacent to at least one node in . A dominating set is called minimal when there does not exist a node such that the set is a dominating set. In this paper, we propose a new self-stabilizing algorithm for minimal dominating set. It has safe convergence property under synchronous daemon in the sense that starting from an arbitrary state, it quickly converges to a dominating set (a safe state) in two rounds, and then stabilizes in a minimal dominating set (the legitimate state) in rounds without breaking safety during the convergence interval, where n is the number of nodes. Space requirement at each node is bits. [ABSTRACT FROM AUTHOR]

Published
2015
Full Text
View/download PDF

4. Efficient self-stabilizing construction of disjoint MDSs in distance-2 model

Author

Johnen, Colette, Haddad, Mohammed, Johnen, Colette, Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID, DistributEd aLgorithms and sYStems (DELYS), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), This study was partially supported by anr project estate : ANR-16-CE25-0009-03., Inria Paris, Sorbonne Université, LaBRI, CNRS UMR 5800, LIRIS UMR CNRS 5205, ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)

Subjects
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Algorithmic graph, Minimal dominating set, Distributed algorithm, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Distance-2 model, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Convergence time, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Maximal independent set, Self-stabilization
Abstract

We study the deterministic silent self-stabilizing construction of two disjoint minimal dominating sets (MDSs) in anonymous networks. We focus on algorithms where nodes share only their status (i.e. the name of their MDS to which they belong, if they belong to a MDS). We prove that such an algorithm cannot be designed in distance-1 model under a central daemon; therefore, we study this problem in the distance-2 model under a central daemon. We present an algorithm building two disjoint minimal dominating sets such that one of them is also a maximal independent set (MIS). Any execution of this algorithm converges in 5n moves. Our approach to compute this value is novel: the number of moves is not computed per node. We propose a second algorithm faster than the first one at the expense of the independence property of one of the constructed sets. A node executes at most 2 moves. If the network is not anonymous, the presented algorithms can be translated into a silent self-stabilizing algorithms converging in O($n$•$m$) moves in the distance-1 model under the distributed daemon where m is the number of edges and n the number of nodes. This improves the complexity of O($n$.$m$) moves of proposed algorithms with the same assumptions.

Published
2021

Catalog

Books, media, physical & digital resources
See catalog results