|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Extending Karger's randomized min-cut Algorithm for a Synchronous Distributed setting | | S. Shine
; K. Muralikrishnan
; | | Date: |
7 Dec 2009 | | Abstract: | A min-cut that seperates vertices s and t in a network is an edge set of
minimum weight whose removal will disconnect s and t. This problem is the dual
of the well known s-t max-flow problem. Several algorithms for the min-cut
problem are based on max-flow computation although the fastest known min-cut
algorithms are not flow based. The well known Karger’s randomized algorithm for
min-cut is a non-flow based method for solving the (global) min-cut problem of
finding the min s-t cut over all pair of vertices s,t in a weighted undirected
graph. This paper presents an adaptation of Karger’s algorithm for a
synchronous distributed setting where each node is allowed to perform only
local computations. The paper essentially addresses the technicalities involved
in circumventing the limitations imposed by a distributed setting to the
working of Karger’s algorithm. While the correctness proof follows directly
from Karger’s algorithm, the complexity analysis differs significantly. The
algorithm achieves the same probability of success as the original algorithm
with O(mn^{2}) message complexity and O(n^{2}) time complexity, where n and m
denote the number of vertices and edges in the graph. | | Source: | arXiv, 0912.1200 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER