BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
BEGIN:VEVENT
UID:496@lincs.fr
DTSTART;TZID=Europe/Paris:20190925T140000
DTEND;TZID=Europe/Paris:20190925T150000
DTSTAMP:20190930T103337Z
URL:https://www.lincs.fr/events/distributed-reconfiguration-of-graph-probl
 ems/
SUMMARY:Distributed Reconfiguration of Graph Problems
DESCRIPTION:\n In Graph Theory\, a reconfiguration problem is as following:
 given two solutions of a problem and a transition definition\, is there a
 path of acceptable solutions from the first to the second using a
 transition one after another? What is the length of the shortest
 reconfiguration path? What complexities are involved? For example\, a
 recoloration problem asks if we can go from a coloration to another\, by
 changing the color of a node at each transition (with the coloring still
 valid in the intermediate steps).In this talk\, the goal would be to
 consider distributed version of two reconfiguration problems: recoloring\,
 and reconfiguring independent sets. To parallelise the process\, we will
 accept to change the state of different nodes at once\, under certain
 hypothesis (for example\, we will recolor an independent set of nodes). The
 questions will be\, using the LOCAL model\, how much communication is
 needed (i.e. how much a node needs knowledge of its neighborhood) in order
 to produce a reconfiguration schedule of a given length.For the distributed
 recoloring (DISC 2019)\, we prove that the addition of colors for the
 intermediate steps is needed for some cases in order to have a solution. I
 will provide the analysis of trees\, where we want to go from a 3-coloring
 to another with the use of a 4th color. II will show that a constant
 schedule can be found after  O(D+log* n)   communications. For the
 reconfiguration of independent sets (ICALP 2019 Best Paper)\, we will
 present different transitions from the centralized settings\, to then
 justify the one we use. We prove that a constant schedule can be found
 after   O(D +log* n)  communications\, and a linear schedule can be found
 after a constant number of communications.\n\n\n\nThose works are the
 result of collaborations with Marthe Bonamy\, Keren Censor-Hillel\, Paul
 Ouvrard\, Jara Uitto and Jukka Suomela \n
CATEGORIES:Seminars,Youtube
LOCATION:Paris-Rennes Room (EIT Digital)\, 23 avenue d'Italie\, 75013
 Paris\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=23 avenue d'Italie\, 75013
 Paris\, France;X-APPLE-RADIUS=100;X-TITLE=Paris-Rennes Room (EIT
 Digital):geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
DTSTART:20190331T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR