BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/931
DTSTAMP:20230914T125943Z
SUMMARY:Succinct Representations of Shortest Paths in Graphs
DESCRIPTION:Speaker: Kshitij Gajjar\n\nAbstract: \nAbstract: Computing and
maintaining shortest paths is a fundamental problem in computer science.
We consider two ways of succinctly representing shortest paths in graphs:
(i) distance-preserving subgraphs\, and (ii) parametric shortest paths. In
this talk\, we will survey our results on these topics. In particular\, w
e will present the following two results in detail.\n(i) Given a graph wit
h $k$ special vertices (called terminals)\, a distance-preserving subgraph
of it is a subgraph which has the same pairwise distances between the ter
minals as in the original graph. We prove that every interval graph with $
k$ terminals has a distance-preserving subgraph with $O(k \\log k)$ vertic
es of degree three or more. We also prove that this bound is tight.\n(ii)
Given a graph with two special vertices $s$ and $t$\, and edge weights tha
t vary linearly with a parameter $\\lambda$\, the parametric shortest path
complexity of the graph is the number of times the shortest $s$-$t$ path
changes as $\\lambda$ varies from $-\\infty$ to $+\\infty$. We construct a
family of planar graphs $(G_n: n\\geq 4)$\, where $G_n$ has $n$ vertices\
, such that the parametric shortest path complexity of $G_n$ is $n^{\\Omeg
a(\\log n)}$. This refutes a conjecture of Nikolova (2009).\n
URL:https://www.tcs.tifr.res.in/web/events/931
DTSTART;TZID=Asia/Kolkata:20190104T171500
DTEND;TZID=Asia/Kolkata:20190104T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR