Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

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.
OriginalsprogEngelsk
Titel2017 IEEE 58th Annual IEEE Symposium on Foundations of Computer Science (FOcS)
ForlagIEEE
Publikationsdato2017
Sider950-961
DOI
StatusUdgivet - 2017
Begivenhed58th Annual IEEE Symposium on Foundations of Computer Science - Berkeley, USA
Varighed: 15 okt. 201717 okt. 2017
Konferencens nummer: 58

Konference

Konference58th Annual IEEE Symposium on Foundations of Computer Science
Nummer58
LandUSA
ByBerkeley
Periode15/10/201717/10/2017

ID: 194948023