Thumbnail
Access Restriction
Open

Author Shine, S. ♦ Krishnan, K. Murali
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2009-12-07
Language English
Subject Domain (in DDC) Computer science, information & general works
Subject Keyword Computer Science - Data Structures and Algorithms ♦ Parallel ♦ and Cluster Computing ♦ Computer Science - Distributed ♦ cs
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.
Educational Use Research
Learning Resource Type Article
Page Count 6


Open content in new tab

   Open content in new tab