Learning Centre

Distributed reconfiguration of maximal independent sets

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Censor-Hillel, Keren
dc.contributor.author Rabie, Mikaël
dc.date.accessioned 2020-04-28T06:31:43Z
dc.date.available 2020-04-28T06:31:43Z
dc.date.issued 2020-09
dc.identifier.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 en
dc.identifier.issn 0022-0000
dc.identifier.other PURE UUID: 3999771c-3d79-481c-9617-ae971a4c5220
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/3999771c-3d79-481c-9617-ae971a4c5220
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85082652155&partnerID=8YFLogxK
dc.identifier.other PURE LINK: https://arxiv.org/abs/1810.02106
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/43848
dc.description | openaire: EC/H2020/755839/EU//BANDWIDTH
dc.description.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. en
dc.language.iso en en
dc.publisher Academic Press Inc.
dc.relation info:eu-repo/grantAgreement/EC/H2020/755839/EU//BANDWIDTH
dc.relation.ispartofseries JOURNAL OF COMPUTER AND SYSTEM SCIENCES en
dc.rights openAccess en
dc.title Distributed reconfiguration of maximal independent sets en
dc.type A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä fi
dc.description.version Peer reviewed en
dc.contributor.department Technion-Israel Institute of Technology
dc.contributor.department Department of Computer Science
dc.subject.keyword Distributed computing
dc.subject.keyword Maximal independent sets
dc.subject.keyword Reconfiguration
dc.identifier.urn URN:NBN:fi:aalto-202004282862
dc.identifier.doi 10.1016/j.jcss.2020.03.003

Files in this item

Files Size Format View

There are no open access files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication