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