Name
Abstract | ||
|---|---|---|
This paper considers fully dynamic graph algorithms with both faster worst case update time and sublinear space. The fully dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes, process an online sequence of edge insertions, edge deletions, and queries of the form "Is there a path between nodes a and b?" In 2013, the first data structure was presented with worst case time per operation which was polylogarithmic in n. In this paper, we shave off a factor of log n from that time, to O(log^4 n) per update. For sequences which are polynomial in length, our algorithm answers queries in O(log n/\log\log n) time correctly with high probability and using O(n \log^2 n) words (of size log n). This matches the amount of space used by the most space-efficient graph connectivity streaming algorithm. We also show that 2-edge connectivity can be maintained using O(n log^2 n) words with an amortized update time of O(log^6 n). |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Sublinear function,Graph algorithms,Graph,Data structure,Discrete mathematics,Binary logarithm,Combinatorics,Streaming algorithm,Polynomial,Connectivity,Mathematics |
DocType | Volume | Citations |
Journal | abs/1509.06464 | 10 |
PageRank | References | Authors |
0.52 | 4 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| david gibb | 1 | 10 | 0.52 |
| Bruce M. Kapron | 2 | 308 | 26.02 |
| Valerie King | 3 | 1276 | 99.39 |
| nolan thorn | 4 | 10 | 0.52 |