Distributed Reconfiguration of Maximal Independent Sets - Inria - Institut national de recherche en sciences et technologies du numérique
Nothing Special   »   [go: up one dir, main page]

Article Dans Une Revue Journal of Computer and System Sciences Année : 2020
Distributed Reconfiguration of Maximal Independent Sets
1 Department of Computer Science [Haifa] (Technion Israel Institute of Technology Haifa 32000 Israel - Israël)
"> Department of Computer Science [Haifa]
2 DELYS - DistributEd aLgorithms and sYStems (2 rue Simone Iff -CS 42112 -75589 Paris Cedex 12 - France)
"> DELYS - DistributEd aLgorithms and sYStems
3 Aalto University (P.O. Box 11000, FI-00076 Aalto - Finlande)
"> Aalto University

Résumé

We investigate a distributed maximal independent set reconfiguration problem, in which there are two MIS for which every node is given its membership status, and the nodes need to communicate with their neighbors to find a reconfiguration schedule from the first MIS to the second. We forbid two neighbors to change their membership status at the same step. We provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O(MIS + R32) rounds. For bounded degree graphs, this is O(log * n) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.
Fichier principal
Vignette du fichier
Journal.pdf (356.28 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02879023 , version 1 (23-06-2020)
Identifiants

Citer

Keren Censor-Hillel, Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. Journal of Computer and System Sciences, 2020, 112, pp.85-96. ⟨10.1016/j.jcss.2020.03.003⟩. ⟨hal-02879023⟩
77 Consultations
121 Téléchargements

Altmetric

Partager

More