Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time. / Nanongkai, Danupon; Saranurak, Thatchaphol; Wulff-Nilsen, Christian.
2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS). IEEE, 2017. p. 950-961.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
AU - Nanongkai, Danupon
AU - Saranurak, Thatchaphol
AU - Wulff-Nilsen, Christian
N1 - Conference code: 58
PY - 2017
Y1 - 2017
N2 - Abstract: We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(no(1)) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n0.5-ε) for some constant ε > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n0.494) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n0.5-ε) in [2] to O(no(1)) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the “contraction technique” by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.
AB - Abstract: We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(no(1)) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n0.5-ε) for some constant ε > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n0.494) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n0.5-ε) in [2] to O(no(1)) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the “contraction technique” by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.
KW - dynamic graph algorithms
KW - minimum spanning forests
KW - graph decomposition
U2 - 10.1109/FOCS.2017.92
DO - 10.1109/FOCS.2017.92
M3 - Article in proceedings
SP - 950
EP - 961
BT - 2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS)
PB - IEEE
Y2 - 15 October 2017 through 17 October 2017
ER -
ID: 194948023