Friday, 15:15 - 15:40 h, Room: H 3013


Nicholas Harvey
Graph sparsifiers


A sparsifier of a graph is a sparse, weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of 1 ± ε. Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc.
We describe a new approach to constructing sparsifiers: by sampling each edge uv with probability inversely proportional to the edge-connectivity between u and v. This results in a sparsifier with O(n log2(n) / ε2) edges, answering a question of Benczur and Karger. A variant of this argument shows that one can obtain sparsifiers by sampling uniformly random spanning trees. Our proofs are based on extensions of Karger's contraction algorithm which allow it to compute minimum "Steiner'' cuts.


Talk 1 of the invited session Fri.3.H 3013
"Flows, cuts, and sparsifiers" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. If you have already decided to take Buy Generic Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.