13 citations · 40 across the 13 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
cs.DS2015
Tight Bounds for Gomory-Hu-like Cut Counting
Rajesh Chitnis, Lior Kamma, Robert Krauthgamer
By a classical result of Gomory and Hu (1961), in every edge-weighted graph , the minimum -cut values, when ranging over all , take at most distinc…
cs.DS2015★ 13 cited
Kernelization via Sampling with Applications to Dynamic Graph Streams
Rajesh Chitnis, Graham Cormode, Hossein Esfandiari +4
In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input…