Random Sampling in Residual Graphs (2008)
David R. Karger, Matthew S. Levine
ABSTRACT Consider an n-vertex, m-edge, undirected graph with maximumflow value v. We give a new ~O (m + nv)-time maximum flow algo-rithm based on finding augmenting paths in random samples of the...
Fast Randomized Algorithms for Computing Minimum {3,4,5,6}-Way Cuts (2007)
A minimum k-way cut of an n-vertex, m-edge, weighted, undirected graph is a partition of the vertices into k sets that minimizes the total weight of edges with endpoints in dierent sets. We give new...
Levine, Matthew S. (Matthew Steven)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.
Levine, Matthew S. (Matthew Steven)
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.
Levine, Matthew S. (Matthew Steven)
We consider two connectivity problems on undirected graphs: maximum flow and minimum k-way cut. The maximum flow problem asks about the connectivity between two specified nodes. A traditional...
Algorithms for Connectivity Problems in . . . (2002)
R. Karger, Matthew S. Levine, Matthew S. Levine
We consider two connectivity problems on undirected graphs: maximum flow and minimum k-way cut.
Finding the Right Cutting Planes for the TSP (1999)
. Given an instance of the Traveling Salesman Problem (TSP), a reasonable way to get a lower bound on the optimal answer is to solve a linear programming relaxation of an integer programming...
Experimental study of minimum cut algorithms / (1997)
Levine, Matthew S. (Matthew Steven)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Experimental study of minimum cut algorithms (1997)
Levine, Matthew S. (Matthew Steven)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Experimental study of minimum cut algorithms (1997)
Levine, Matthew S. (Matthew Steven)
Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1997.
Experimental study of minimum cut algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...
Experimental Study of Minimum Cut Algorithms (1997)
David R. Karger, Arthur C. Smith, Matthew S. Levine, Matthew S. Levine
Experimental Study of Minimum Cut Algorithms (1997)
Matthew S. Levine, Matthew S. Levine
Requirements for the Degree of Master of Science in Computer Science Recently, several new algorithms have been developed for the minimum cut problem that substantially improve worst-case time bounds...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve the...
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (1997)
David R. Karger, Matthew S. Levine
Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n p v)) time per path. This lets us...
Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching (1997)
David Karger, Matthew S. Levine
Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n p v)) time per path. This lets us...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...
Experimental Study of Minimum Cut Algorithms (1997)
Chandra Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, Cliff Stein
Recently, several new algorithms have been developed for the minimum cut problem. These algorithms are very different from the earlier ones and from each other and substantially improve worst-case...