BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/450
DTSTAMP:20230914T125925Z
SUMMARY:Preserving Terminal Distances Using Minors
DESCRIPTION:Speaker: Kshitij  Gajjar\n\nAbstract: \nAbstract: We ask the fo
 llowing question: given a network with a large number of nodes\, edges wit
 h nonnegative costs on them and a small set of special nodes called termin
 als\, by how much can we compress the graph such that the shortest distanc
 e between any pair of terminals remains the same? We are allowed to perfor
 m a sequence of the following operations:\n(1) Delete an edge (this reduce
 s the number of edges by 1)\n(2) Contract (or shrink) an edge into a singl
 e node (this reduces the number of edges and number of nodes by 1)\n(3) Ch
 ange edge cost arbitrarily\, as long as it remains nonnegative\nFormally s
 tated\, for any family $\\mathcal{F}$ of undirected graphs\, what is the s
 mallest $f(k\,\\mathcal{F})$ such that every graph $G(V\,E) \\in\n\\mathca
 l{F}$ with nonnegative weights on the edges and a set of terminal nodes $R
  \\subseteq V$ having $|R|=k$ admits a distance preserving minor with at m
 ost $f(k\,\\mathcal{F})$ nodes? (Observe that $f$ does not depend on the t
 otal number of nodes in the original graph).\nIn this talk\, we will be de
 fining the terms minor and distance preserving minor with examples. If $\\
 mathcal{G}$ is the family of all undirected\ngraphs\, $\\mathcal{P}$ is th
 e family of all planar graphs and $\\mathcal{T}$ is the family of all tree
 s\, we will show that:\n$f(k\,\\mathcal{G}) \\leq k^{4}$\n$f(k\,\\mathcal{
 P}) \\geq c \\cdot k^{2}$ (for some constant $c$)\n$f(k\,\\mathcal{T})=2k-
 2$\nThis is due to recent work by Robert Krauthgamer and Tamar Zondiner.\n
URL:https://www.tcs.tifr.res.in/web/events/450
DTSTART;TZID=Asia/Kolkata:20140131T140000
DTEND;TZID=Asia/Kolkata:20140131T150000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR