BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/970
DTSTAMP:20230914T125945Z
SUMMARY:Finding Optimal Shortest Path Trees
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nAbstract: Given a graph
  $G$ with one source vertex $s$ and several target vertices\, a shortest p
 ath tree rooted at $s$ is a subgraph of $G$ that preserves distances from 
 $s$ to each of the target vertices. A shortest path tree is called optimal
  if it has the minimum number of branching vertices (vertices of degree th
 ree or more). In this talk\, we will see proofs of the following results.\
 n1. Finding an optimal shortest path tree is $\\mathsf{NP}$-hard for gener
 al graphs.\n2. Finding an optimal shortest path tree is in $\\mathsf{P}$ f
 or interval graphs.\nThis is based on joint work with Jaikumar. A condense
 d version of this talk will be given at CSR 2019 in Novosibirsk\, Russia.\
 n
URL:https://www.tcs.tifr.res.in/web/events/970
DTSTART;TZID=Asia/Kolkata:20190614T171500
DTEND;TZID=Asia/Kolkata:20190614T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR