15 citations · 15 across the 1 of their papers we have counts for
4 papers · 1 filter
Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
Andras Benczur, David R. Karger
We improve on random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time construction that transforms any graph…
Approximate Graph Coloring by Semidefinite Programming
David Karger, Rajeev Motwani, Madhu Sudan
We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on ver…
Minimum Cuts in Near-Linear Time
David R. Karger
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a ``semi-duality'' between minimum cuts and maximum spanning tree packin…
A Fully Polynomial Randomized Approximation Scheme for the All Terminal Network Reliability Problem
David R. Karger
The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability.