Average Update Times for Fully-Dynamic All-Pairs Shortest Paths

DOI10.1007/978-3-540-92182-0_61MaRDI QIDQ3596762zbMATH OpenOpenAlexFDO

Authors Tobias Friedrich, Nils Hebbinghaus

Publication date 29 January 2009

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-92182-0_61

zbMATH Keywords

average-case analysisdynamic graph algorithmsrandom graphsshortest paths

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

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

Cited in

(4)

• Dynamic single-source shortest paths in Erdős-Rényi random graphs
• Worst-case update times for fully-dynamic all-pairs shortest paths
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• Average 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 Q3596762)