Average update times for fully-dynamic all-pairs shortest paths
From MaRDI portal
Publication:643013
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
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
