Distributed recoloring

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Bonamy, Marthe
dc.contributor.author Ouvrard, Paul
dc.contributor.author Rabie, Mikaël
dc.contributor.author Suomela, Jukka
dc.contributor.author Uitto, Jara
dc.contributor.editor Schmid, Ulrich
dc.contributor.editor Widder, Josef
dc.date.accessioned 2019-02-25T08:54:27Z
dc.date.available 2019-02-25T08:54:27Z
dc.date.issued 2018-10-01
dc.identifier.citation Bonamy , M , Ouvrard , P , Rabie , M , Suomela , J & Uitto , J 2018 , Distributed recoloring . in U Schmid & J Widder (eds) , 32nd International Symposium on Distributed Computing, DISC 2018 . , 12 , Leibniz International Proceedings in Informatics (LIPIcs) , vol. 121 , Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , pp. 1-17 , International Symposium on Distributed Computing , New Orleans , United States , 15/10/2018 . https://doi.org/10.4230/LIPIcs.DISC.2018.12 en
dc.identifier.isbn 9783959770927
dc.identifier.issn 1868-8969
dc.identifier.other PURE UUID: da348444-389c-4dbe-abb4-530ed2c6ca12
dc.identifier.other PURE ITEMURL: https://research.aalto.fi/en/publications/distributed-recoloring(da348444-389c-4dbe-abb4-530ed2c6ca12).html
dc.identifier.other PURE LINK: http://www.scopus.com/inward/record.url?scp=85059611983&partnerID=8YFLogxK
dc.identifier.other PURE FILEURL: https://research.aalto.fi/files/31378729/LIPIcs_DISC_2018_12_1.pdf
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/36911
dc.description.abstract Given two colorings of a graph, we consider the following problem: can we recolor the graph from one coloring to the other through a series of elementary changes, such that the graph is properly colored after each step? We introduce the notion of distributed recoloring: The input graph represents a network of computers that needs to be recolored. Initially, each node is aware of its own input color and target color. The nodes can exchange messages with each other, and eventually each node has to stop and output its own recoloring schedule, indicating when and how the node changes its color. The recoloring schedules have to be globally consistent so that the graph remains properly colored at each point, and we require that adjacent nodes do not change their colors simultaneously. We are interested in the following questions: How many communication rounds are needed (in the deterministic LOCAL model of distributed computing) to find a recoloring schedule? What is the length of the recoloring schedule? And how does the picture change if we can use extra colors to make recoloring easier? The main contributions of this work are related to distributed recoloring with one extra color in the following graph classes: trees, 3-regular graphs, and toroidal grids. en
dc.format.extent 1-17
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Schloss Dagstuhl--Leibniz-Zentrum für Informatik
dc.relation.ispartof International Symposium on Distributed Computing en
dc.relation.ispartofseries 32nd International Symposium on Distributed Computing, DISC 2018 en
dc.relation.ispartofseries Leibniz International Proceedings in Informatics (LIPIcs) en
dc.relation.ispartofseries Volume 121 en
dc.rights openAccess en
dc.subject.other Software en
dc.subject.other Computational Theory and Mathematics en
dc.subject.other 113 Computer and information sciences en
dc.subject.other Theoretical computer science en
dc.title Distributed recoloring en
dc.type A4 Artikkeli konferenssijulkaisussa fi
dc.description.version Peer reviewed en
dc.contributor.department Universite de Bordeaux
dc.contributor.department Professorship Suomela J.
dc.contributor.department Swiss Federal Institute of Technology Zurich
dc.contributor.department Department of Computer Science en
dc.subject.keyword And phrases Distributed Systems
dc.subject.keyword Graph Algorithms
dc.subject.keyword Local Computations
dc.subject.keyword Software
dc.subject.keyword Computational Theory and Mathematics
dc.subject.keyword 113 Computer and information sciences
dc.subject.keyword Theoretical computer science
dc.identifier.urn URN:NBN:fi:aalto-201902252068
dc.identifier.doi 10.4230/LIPIcs.DISC.2018.12
dc.type.version publishedVersion

Files in this item

Files Size Format View

There are no 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


My Account