Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing |
| Number of pages | 14 |
| Publisher | Association for Computing Machinery |
| Publication date | 2017 |
| Pages | 1130-1143 |
| ISBN (Electronic) | 978-1-4503-4528-6 |
| DOIs | |
| Publication status | Published - 2017 |
| Event | 49th Annual ACM SIGACT Symposium on Theory of Computing - Montreal, Canada Duration: 19 Jun 2017 → 23 Jun 2017 Conference number: 49 |
Conference
| Conference | 49th Annual ACM SIGACT Symposium on Theory of Computing |
|---|---|
| Number | 49 |
| Country/Territory | Canada |
| City | Montreal |
| Period | 19/06/2017 → 23/06/2017 |
Keywords
- Dynamic graph connectivity
- Dynamic minimum spanning forest