| Title | : | New results and techniques for finding min-cuts in the CONGEST Model |
| Speaker | : | Mohit Daga (IITM) |
| Details | : | Wed, 2 Aug, 2017 3:00 PM @ Turing Hall |
| Abstract: | : | Finding small min-cuts for a network is essential for ensuring the quality of service and reliability. The so called CONGEST model for distributed networks is suited for analysing algorithms for networks. In this work, we give deterministic algorithms for finding min-cuts in the CONGEST Model. We improve upon the results of a decade old work by Pritchard and Thurimella. They use random circulation technique and give Las Vegas type algorithm to find min-cut of size 1 and 2 in O(D) where D is the diameter of the network. On the contrary, we provide deterministic algorithms to find all the min-cuts of size 1 and 2 in O(D) time and min-cuts of size 3 in O(D^2) time. We introduce several novel techniques including a tree restricted semi group function, a sketching technique, and a layered algorithm which might also be of independent future use for distributed algorithms on networks. |
