Distributed reconfiguration of maximal independent sets
Loading...
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
Other link related to publication (opens in new window)
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
12
Series
Journal of Computer and System Sciences, Volume 112, pp. 85-96
Abstract
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.Description
| openaire: EC/H2020/755839/EU//BANDWIDTH
Other note
Citation
Censor-Hillel, K & Rabie, M 2020, 'Distributed reconfiguration of maximal independent sets', Journal of Computer and System Sciences, vol. 112, pp. 85-96. https://doi.org/10.1016/j.jcss.2020.03.003