15 citations · 15 across the 2 of their papers we have counts for
Showing 1998Show all
3 papers · 1 filter
cs.DS1998
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…
cs.DS1998
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…
cs.DS1998
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.