BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/645
DTSTAMP:20230914T125932Z
SUMMARY:Distance Preserving Minors in Interval Graphs
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nAbstract: We consider u
 ndirected\, connected graphs with nonnegative weights on the edges. Additi
 onally\, a special subset of vertices called terminals is provided as inpu
 t. A graph $H$ is said to be a distance preserving minor of $G$ if: (i) $H
 $ is a minor of $G$\, and (ii) the distance between each pair of terminals
  is exactly the same in $G$ and $H$. Note that the edge weights can be rea
 ssigned in $H$ (as long as they are nonnegative). Given a family of graphs
  $\\mathcal{F}$\, let $f(k\,\\mathcal{F})$ be the minimum integer such tha
 t every graph in $\\mathcal{F}$ with $k$ terminals admits a distance prese
 rving minor with at most $f(k\,\\mathcal{F})$ vertices.\n\nIn this work\, 
 we explore interval graphs. Given an interval graph $G$ on $k$ terminals\,
  we describe a method of producing a distance preserving minor of $G$ havi
 ng at most $k^2$ vertices. Thus\, $f(k\,\\mathcal{I})\\le k^2$\, where $\\
 mathcal{I}$ is the family of all interval graphs. We also show that there 
 are interval graphs on which our method does not perform optimally. In par
 ticular\, there exists an interval graph which admits a distance preservin
 g minor of size $O(k\\log k)$\, but our method produces a distance preserv
 ing minor of size $\\Omega(k^2)$ for it. Thus\, the problem of finding an 
 optimal distance preserving minor for interval graphs remains open.\n \n
URL:https://www.tcs.tifr.res.in/web/events/645
DTSTART;TZID=Asia/Kolkata:20160109T100000
DTEND;TZID=Asia/Kolkata:20160109T110000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR