Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

• DOI: 10.1109/focs.2017.92
• Publication Date: 2017-11-14T13:59:34Z
• Authors: Danupon Nanongkai; Thatchaphol Saran...; Christian Wulff-N...
• Keywords: minimum spanning forests; FOS: Computer and information sciences; dynamic graph algorithms; Computer Science - Data Structures and Algorithms; 0202 electrical engineering, electronic engineering, information engineering; Data Structures and Algorithms (cs.DS); 0102 computer and information sciences; 02 engineering and technology; graph decomposition; 01 natural sciences

We present a Las Vegas algorithm for dynamically maintaining minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our guarantees O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(1)</sup> ) worst-case update time with high probability. This significantly improves the two recent algorithms by Wulff-Nilsen [2] xmlns:xlink="http://www.w3.org/1999/xlink">0.5-ε</sup> some constant ε > 0 and, independently, Nanongkai Saranurak [3] xmlns:xlink="http://www.w3.org/1999/xlink">0.494</sup> (the latter works only forest). result is obtained identifying common framework that both previous rely on, then improve combine ideas from works. There are main algorithmic components newly improved critical obtaining our result. First, we in to decrementally removing all low-conductance cuts expander Second, revisiting "contraction technique" Henzinger King [4] Holm et al. [5], show new approach connected graphs very few (at most (1 + o(1))n) edges. [2], which based on Frederickson's 2-dimensional topology tree [6] illustrates application this old technique.