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

DOI10.1016/j.dam.2011.02.007zbMath1228.05272OpenAlexW2003580987MaRDI QIDQ643013

Nils Hebbinghaus, Tobias Friedrich

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

random graphsshortest pathsaverage-case analysisdynamic graph algorithms

Mathematics Subject Classification ID

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

Cites Work

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

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