Fully-dynamic minimum spanning forest with improved worst-case update time
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Fully-dynamic minimum spanning forest with improved worst-case update time. / Wulff-Nilsen, Christian.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2017. p. 1130-1143.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Fully-dynamic minimum spanning forest with improved worst-case update time
AU - Wulff-Nilsen, Christian
N1 - Conference code: 49
PY - 2017
Y1 - 2017
N2 - We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1/2-c) worst-case time wh.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of Eppstein et al., a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time.
AB - We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1/2-c) worst-case time wh.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of Eppstein et al., a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time.
KW - Dynamic graph connectivity
KW - Dynamic minimum spanning forest
UR - http://www.scopus.com/inward/record.url?scp=85024397829&partnerID=8YFLogxK
U2 - 10.1145/3055399.3055415
DO - 10.1145/3055399.3055415
M3 - Article in proceedings
AN - SCOPUS:85024397829
SP - 1130
EP - 1143
BT - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
PB - Association for Computing Machinery
Y2 - 19 June 2017 through 23 June 2017
ER -
ID: 184140772