Experimental analysis of dynamic all pairs shortest path algorithms

DOI10.1145/1198513.1198519MaRDI QIDQ2944531zbMATH OpenOpenAlexWikidataFDO

Authors Camil Demetrescu, Giuseppe F. Italiano

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

dynamic graph algorithmsexperimental algorithmicsshortest paths

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 6469167
• Power balance and apportionment algorithms for the United States Congress
• A new approach to dynamic all pairs shortest paths
• A new approach to dynamic all pairs shortest paths
• Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?

Cited in

(15)

• Efficient algorithms for updating betweenness centrality in fully dynamic graphs
• Group planning with time constraints
• Partially dynamic efficient algorithms for distributed shortest paths
• Solving all-pairs shortest path by single-source computations: theory and practice
• A new approach to dynamic all pairs shortest paths
• A preliminary analysis of the distance based critical node problem
• A forward-backward single-source shortest paths algorithm
• Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
• Power balance and apportionment algorithms for the United States Congress
• scientific article; zbMATH DE number 6469167 (Why is no real title available?)
• Modifications of the Floyd-Warshall algorithm with nearly quadratic expected-time
• On dynamic shortest paths problems
• Average update times for fully-dynamic all-pairs shortest paths
• \(f\)-sensitivity distance oracles and routing schemes
• Maintaining dynamic minimum spanning trees: an experimental study

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2944531)