2016/11/09 by Christian Wulff‐Nilsen, Wulff-Nilsen, Christian · 3 citations
Computer Science · #Caching and Content Delivery #Advanced Data Storage Technologies #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.1611.02864
We give a Las Vegas data structure which maintains a minimum spanning forest\nin an n-vertex edge-weighted dynamic graph undergoing updates consisting of any\nmixture of edge insertions and deletions. Each update is supported in O(n1/2\n- c) expected worst-case time for some constant c > 0 and this worst-case\nbound holds with probability at least 1 - n-d where d is a constant that can\nbe made arbitrarily large. This is the first data structure achieving an\nimprovement over the O(n1/2) deterministic worst-case update time of\nEppstein et al., a bound that has been standing for nearly 25 years. In fact,\nit was previously not even known how to maintain a spanning forest of an\nunweighted graph in worst-case time polynomially faster than Theta(n1/2).\nOur result is achieved by first giving a reduction from fully-dynamic to\ndecremental minimum spanning forest preserving worst-case update time up to\nlogarithmic factors. Then decremental minimum spanning forest is solved using\nseveral novel techniques, one of which involves keeping track of\nlow-conductance cuts in a dynamic graph. An immediate corollary of our result\nis the first Las Vegas data structure for fully-dynamic connectivity where each\nupdate is handled in worst-case time polynomially faster than Theta(n1/2)\nw.h.p.; this data structure has O(1) worst-case query time.\n