The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Vertex sparsifiers: New results from old techniques (and some open questions)

Krauthgamer, R (Weizmann Institute of Science)
Monday 10 January 2011, 11:30-12:30

Seminar Room 1, Newton Institute


Given a capacitated graph G = (V,E) and a set of terminals $K \subseteq V$, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a ``simple'' graph? What if we allow H to be a convex combination of simple graphs? And is the question easier if we wanted H to maintain the distances among the terminals (rather than flows)?

Joint work with Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Raecke, Inbal Talgam-Cohen and Kunal Talwar.


[pps ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧