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