A new approach to dynamic all pairs shortest paths
From MaRDI portal
Publication:5435671
DOI10.1145/1039488.1039492zbMath1125.68393OpenAlexW1982440947WikidataQ61609608 ScholiaQ61609608MaRDI QIDQ5435671
Giuseppe F. Italiano, Camil Demetrescu
Publication date: 14 January 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1039488.1039492
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (47)
The impact of dynamic events on the number of errors in networks ⋮ On the robustness of the metric dimension of grid graphs to adding a single edge ⋮ Optimal length resolution refutations of difference constraint systems ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Dynamic shortest paths and transitive closure: algorithmic techniques and data structures ⋮ Dynamic Single-Source Shortest Paths in Erdös-Rényi Random Graphs ⋮ Decremental algorithm for adaptive routing incorporating traveler information ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ Unnamed Item ⋮ Unit read-once refutations for systems of difference constraints ⋮ Optimizing the ecological connectivity of landscapes ⋮ Unnamed Item ⋮ Approximate shortest paths avoiding a failed vertex: near optimal data structures for undirected unweighted graphs ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Finding large \(k\)-clubs in undirected graphs ⋮ Improved distance sensitivity oracles with subcubic preprocessing time ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Efficient algorithms for updating betweenness centrality in fully dynamic graphs ⋮ Computing inversion pair cardinality through partition-based sorting ⋮ Incremental single-source shortest paths in digraphs with arbitrary positive arc weights ⋮ A mechanical verification of the stressing algorithm for negative cost cycle detection in networks ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs ⋮ Partially dynamic efficient algorithms for distributed shortest paths ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On approximating optimal weight ``no-certificates in weighted difference constraint systems ⋮ Randomization for Efficient Dynamic Graph Algorithms ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ Disk-based shortest path discovery using distance index over large dynamic graphs ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Unnamed Item ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization ⋮ Analyzing unit read-once refutations in difference constraint systems ⋮ On memoryless provers and insincere verifiers ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Fault tolerant sorting -- theoretical and empirical analyses of the randomized quickmergesort algorithm ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
This page was built for publication: A new approach to dynamic all pairs shortest paths
