08/07/2020

Minimum cut in O(m log² n) time

Pawel Gawrychowski, Shay Mozes and Oren Weimann

Keywords: Minimum cut, Minimum 2-respecting cut

Abstract Paper Similar Papers

Abstract: We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m log² n) time. This is the first improvement to Karger’s celebrated O(m log³ n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.

 0
 0
 0
 0
  Share    
This is an embedded video. Talk and the respective paper are published at ICALP 2020 virtual conference. If you are one of the authors of the paper and want to manage your upload, see the question "My papertalk has been externally embedded..." in the FAQ section.

Comments

Post Comment
no comments yet
code of conduct: tbd Characters remaining: 140

Similar Papers

 0
 0
 0
 0
 25:12 
 0
 0
 0
 0
 17:26 
 0
 0
 0
 0
 21:14 
 0
 0
 0
 0
 25:12 
 0
 0
 0
 0
 14:49 
 0
 0
 0
 0
 24:32 
 0
 0
 0
 0
 21:18 
 0
 0
 0
 0
 23:57 
 0
 0
 0
 0
 25:15 
 0
 0
 0
 0
 21:47 
 0
 0
 0
 0
 23:58 
 0
 0
 0
 0
 26:15 
 0
 0
 0
 0
 19:50 
 0
 0
 0
 0
 26:02 
 0
 0
 0
 0
 18:42 
 0
 0
 0
 0
 23:42 
 0
 0
 0
 0
 25:05 
 0
 0
 0
 0
 22:17 
 0
 0
 0
 0
 29:37 
 0
 0
 0
 0
 25:08 
 0
 0
 0
 0
 24:16 
 0
 0
 0
 0
 21:27 
 0
 0
 0
 0
 6:50 
 0
 0
 0
 0
 5:25 
 0
 0
 0
 0
 15:28 
 0
 0
 0
 0
 24:42 
 0
 0
 0
 0
 20:53 
 0
 0
 0
 0
 12:54 
 0
 0
 0
 0
 5:16 
 0
 0
 0
 0
 24:48 
 0
 0
 0
 0
 21:34 
 0
 0
 0
 0
 25:55 
 0
 0
 0
 0
 20:42 
 0
 0
 0
 0
 25:01 
 0
 0
 0
 0
 23:50 
 0
 0
 0
 0
 9:20 
 0
 0
 0
 0
 27:40 
 0
 0
 0
 0
 17:26 
 0
 0
 0
 0
 12:34 
 0
 0
 0
 0
 23:19