Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut.

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 approach is to search for augmenting paths. We explore the possibility of restricting the set of edges in which we search for an augmenting path, so that we can find each flow path in sub-linear time. Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give two methods for finding augmenting paths in such a graph in amortized sub-linear time, based on the idea that undirected graphs have sparse subgraphs that capture connectivity information. The first method sparsifies unused edges by using a spanning forest. It is deterministic and takes ... time per path on average. The second method sparsifies the entire residual graph by taking random samples of the edges. It takes O(n) time per path on average. These results let us improve the O(mv) time bound of the classic augmenting path algorithm to O(m + nv3/2) (deterministic) and O(m + nv) (randomized). For simple graphs, the addition of a blocking flow subroutine yields a deterministic O (nm2/3vl/6)-time algorithm. 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 different sets. We give new randomized algorithms to find minimum 3-way and 4-way cuts, which lead to time bounds of O(mnk-2 log3 n) for k =/< 6. Our key insight is that two different structural properties of k-way cuts, both exploited by previous algorithms, can be exploited simultaneously to avoid the bottleneck operations in both prior algorithms. The result is that we improve on the best previous time bounds by a factor of O(n2).

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2002

Author dc:creator

• Levine, Matthew S. (Matthew Steven)

Advisor dc:contributor.advisor

• David R. Karger.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/29234

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/29234