Experimental analysis of dynamic all pairs shortest path algorithms

DOI10.1145/1198513.1198519zbMath1321.05257OpenAlexW1991778515WikidataQ61609586 ScholiaQ61609586MaRDI QIDQ2944531

Giuseppe F. Italiano, Camil Demetrescu

Publication date: 2 September 2015

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

shortest pathsexperimental algorithmicsdynamic graph algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (10)

Solving all-pairs shortest path by single-source computations: theory and practice ⋮ On dynamic shortest paths problems ⋮ Average update times for fully-dynamic all-pairs shortest paths ⋮ A preliminary analysis of the distance based critical node problem ⋮ Efficient algorithms for updating betweenness centrality in fully dynamic graphs ⋮ Group planning with time constraints ⋮ \(f\)-sensitivity distance oracles and routing schemes ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ A Forward-Backward Single-Source Shortest Paths Algorithm ⋮ Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time

This page was built for publication: Experimental analysis of dynamic all pairs shortest path algorithms