Conference Paper open access publication

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

Institute of Electrical and Electronics Engineers (IEEE),

2017

DOI:10.1109/focs.2017.92, Dimensions: pub.1095852551,

Affiliations

Organisations

  1. (1) Royal Institute of Technology, grid.5037.1
  2. (2) University of Copenhagen, grid.5254.6, KU

Countries

Sweden

Denmark

Continents

Europe

Description

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an $n$-node graph undergoing edge insertions and deletions. Our algorithm guarantees an $O(n^{o(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(n^{0.5-\epsilon})$-for some constant $\epsilon > 0$ and, independently, by Nanongkai and Saranurak [3] with update time $O(n^{0.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(n^{0.5-\epsilon})$ in [2] to $O(n^{o(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.

Funders

Research Categories

Main Subject Area

Links & Metrics

NORA University Profiles

University of Copenhagen

Dimensions Citation Indicators

Times Cited: 9

Field Citation Ratio (FCR): 5.71

Open Access Info

Green, Submitted