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