Vertex sparsifiers: New results from old techniques (and some open questions)
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Mustapha Amrani.
Discrete Analysis
Given a capacitated graph G = (V,E) and a set of terminals $K ubseteq 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 flowsparsifier 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 TalgamCohen and Kunal Talwar.
This talk is part of the Isaac Newton Institute Seminar Series series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
