Maintaining shortest paths under deletions in weighted directed graphs

DOI10.1145/2488608.2488701zbMath1293.05174OpenAlexW1975344016MaRDI QIDQ5495843

Aaron Bernstein

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488701

zbMATH Keywords

shortest pathsapproximation algorithmsdynamic algorithms

Mathematics Subject Classification ID

Paths and cycles (05C38) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20) Randomized algorithms (68W20) Signed and weighted graphs (05C22)

Related Items

Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs, Single-source shortest paths in the CONGEST model with improved bounds, Distributed distance computation and routing with small messages, Incremental single-source shortest paths in digraphs with arbitrary positive arc weights, Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs, A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates, Dynamically Maintaining Shortest Path Trees under Batches of Updates