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