[Colloquium] REMINDER: 8/31 TTIC Colloquium: Robert Krauthgamer, Weizmann Institute of Science
Mary Marre
mmarre at ttic.edu
Sun Aug 30 18:28:40 CDT 2015
When: Monday, August 31st at 11:00 a.m.
Where: TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526
Speaker: Robert Krauthgamer, Weizmann Institute of Science
Title: Vertex Sparsification of Cuts, Flows, and Distances
Abstract:
A key challenge in designing graph algorithms is to "compress" a graph G
so as to preserve some of its basic properties, such as distances and cuts.
Both spanners [Peleg and Schaffer, 1989] and cut sparsifiers [Benczur and
Karger, 1996] fall into this category, as they reduce the number of edges
in G without changing any distance or cut by more than a small factor.
I will discuss another flavor of this challenge, which asks instead to
reduce the number of vertices. Specifically, given a graph G and k
terminal vertices, we wish to construct a small graph G' that contains
the terminals, such that all cuts/flows/distances between the terminals
are equal in G and in G'. Can we bound the size of G' by a function of k?
And what if G' only needs to approximate G (say within 1+epsilon)?
I plan to survey recent progress in this emerging area.
*Host:* Julia Chuzhoy
For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php
Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*Chicago, IL 60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150830/2cd52a66/attachment.htm
More information about the Colloquium
mailing list