BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1191
DTSTAMP:20230914T125954Z
SUMMARY:Reconfiguring Shortest Paths in Graphs
DESCRIPTION:Speaker: Kshitij Gajjar (National University of Singapore)\n\nA
 bstract: \nReconfiguring a system (generally represented by a graph) means
  gradually transforming one configuration of the system to another configu
 ration by modifying it in a slow and steady step-by-step manner. In the Sh
 ortest Path Reconfiguration (SPR) problem\, we are given two shortest path
 s\, and the goal is to transform one shortest path to the other by changin
 g one vertex at a time\, so that all the intermediate configurations are a
 lso shortest paths. SPR has many real-world applications like repaving roa
 ds in a systematic way\, rerouting messages across a network of telecommun
 ication towers\, cargo container stowage on ships\, train marshalling\, an
 d rerouting data packets across servers in a synchronous multiprocessor se
 tting.\n\nIn this talk\, we will show how one of these applications can be
  modelled by a specific class of graphs\, and then we will solve SPR for t
 hat graph class. We will also show that if we are allowed to change two ve
 rtices at a time\, then SPR becomes PSPACE-complete\, even for a graph cla
 ss for which SPR is known to be solvable in polynomial time when we are al
 lowed to change only one vertex at a time. This is joint work with Agastya
  Vibhuti Jha\, Manish Kumar and Abhiruk Lahiri (https://arxiv.org/abs/2112
 .07499).\nZoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmh
 NYTJGQTF6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1191
DTSTART;TZID=Asia/Kolkata:20220304T161500
DTEND;TZID=Asia/Kolkata:20220304T171500
LOCATION:Via Zoom
END:VEVENT
END:VCALENDAR