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

DOI10.1016/J.DAM.2011.02.007zbMATH Open1228.05272OpenAlexW2003580987MaRDI QIDQ643013FDOQ643013

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

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

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)

Cites Work

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

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)