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