Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut.
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/29234 |
| _version_ | 1826192167438123008 |
|---|---|
| author | Levine, Matthew S. (Matthew Steven) |
| author2 | David R. Karger. |
| author_facet | David R. Karger. Levine, Matthew S. (Matthew Steven) |
| author_sort | Levine, Matthew S. (Matthew Steven) |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002. |
| first_indexed | 2024-09-23T09:07:14Z |
| format | Thesis |
| id | mit-1721.1/29234 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T09:07:14Z |
| publishDate | 2005 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/292342019-04-10T18:34:30Z Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. Levine, Matthew S. (Matthew Steven) David R. Karger. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002. In title on t.p., "[kappa]" apears as lower-case Greek letter. Includes bibliographical references (p. [69]-72). 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). Ph.D. 2005-10-14T19:21:03Z 2005-10-14T19:21:03Z 2002 2002 Thesis http://hdl.handle.net/1721.1/29234 51458636 eng 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. http://dspace.mit.edu/handle/1721.1/7582 72 p. 3419122 bytes 3418927 bytes application/pdf application/pdf application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Levine, Matthew S. (Matthew Steven) Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title | Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title_full | Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title_fullStr | Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title_full_unstemmed | Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title_short | Algorithms for connectivity problems in undirected graphs : maximum flow and minimun [kappa]-way cut. |
| title_sort | algorithms for connectivity problems in undirected graphs maximum flow and minimun kappa way cut |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/29234 |
| work_keys_str_mv | AT levinematthewsmatthewsteven algorithmsforconnectivityproblemsinundirectedgraphsmaximumflowandminimunkappawaycut |