Average update times for fully-dynamic all-pairs shortest paths

DOI10.1016/J.DAM.2011.02.007MaRDI QIDQ643013zbMATH OpenOpenAlexFDO

Authors Tobias Friedrich, Nils Hebbinghaus

Publication date 27 October 2011

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2011.02.007

zbMATH Keywords

shortest pathsaverage-case analysisrandom graphsdynamic graph algorithms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Paths and cycles (05C38)

Recommendations

• Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• All-pairs shortest paths in \(O(n^2)\) time with high probability
• A new approach to dynamic all pairs shortest paths

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 1305092 (Why is no real title available?)
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• A new approach to all-pairs shortest paths on real-weighted graphs
• A new approach to dynamic all pairs shortest paths
• A new upper bound on the complexity of the all pairs shortest path problem
• Algorithm Theory - SWAT 2004
• Algorithms – ESA 2004
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
• Critical random graphs and the structure of a minimum spanning tree
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Experimental analysis of dynamic all pairs shortest path algorithms
• On the computational complexity of dynamic graph problems
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Paths in graphs
• The critical random graph, with martingales
• The diameter of sparse random graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths

Cited in

(4)

• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths

This page was built for publication: Average update times for fully-dynamic all-pairs shortest paths

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