Worst-case update times for fully-dynamic all-pairs shortest paths
From MaRDI portal
Publication:3581384
DOI10.1145/1060590.1060607zbMath1192.68493OpenAlexW2058084873MaRDI 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
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (20)
Distance oracles for time-dependent networks ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ Unnamed Item ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ On the complexity of time-dependent shortest paths ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Efficient algorithms for updating betweenness centrality in fully dynamic graphs ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Dynamic Approximate Vertex Cover and Maximum Matching ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved Dynamic Graph Coloring ⋮ Unnamed Item ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks
This page was built for publication: Worst-case update times for fully-dynamic all-pairs shortest paths
