Worst-case update times for fully-dynamic all-pairs shortest paths
From MaRDI portal
Publication:3581384
DOI10.1145/1060590.1060607zbMath1192.68493MaRDI QIDQ3581384
Publication date: 16 August 2010
Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1060590.1060607
68W05: Nonnumerical algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, Dynamic Approximate Vertex Cover and Maximum Matching, Improved Dynamic Graph Coloring, Decremental SPQR-trees for Planar Graphs, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Unnamed Item, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Distance oracles for time-dependent networks, On the complexity of time-dependent shortest paths, Incremental single-source shortest paths in digraphs with arbitrary positive arc weights, Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs, Average update times for fully-dynamic all-pairs shortest paths, \(f\)-sensitivity distance oracles and routing schemes, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, Efficient algorithms for updating betweenness centrality in fully dynamic graphs, Single-source shortest paths and strong connectivity in dynamic planar graphs, Approximating dynamic weighted vertex cover with soft capacities, Randomization for Efficient Dynamic Graph Algorithms, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs
