Average update times for fully-dynamic all-pairs shortest paths
type: Item
instance of: scholarly article
title: Average update times for fully-dynamic all-pairs shortest paths
zbMATH Open document ID: 1228.05272
author: Tobias Friedrich
author: Nils Hebbinghaus
published in: Discrete Applied Mathematics
publication date: 2011-10-27T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5964713
zbMATH Keywords: dynamic graph algorithms
zbMATH Keywords: shortest paths
zbMATH Keywords: average-case analysis
zbMATH Keywords: random graphs
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2011.02.007
OpenAlex ID: W2003580987
cites work: Critical random graphs and the structure of a minimum spanning tree
cites work: Paths in graphs
cites work: The diameter of sparse random graphs
cites work: A new approach to dynamic all pairs shortest paths
cites work: Experimental analysis of dynamic all pairs shortest path algorithms
cites work: Q3267900
cites work: Average Update Times for Fully-Dynamic All-Pairs Shortest Paths
cites work: Q4252034
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
cites work: The critical random graph, with martingales
cites work: A new approach to all-pairs shortest paths on real-weighted graphs
cites work: On the computational complexity of dynamic graph problems
cites work: A fully dynamic reachability algorithm for directed graphs with an almost linear update time
cites work: Algorithms – ESA 2004
cites work: Dynamic approximate all-pairs shortest paths in undirected graphs
cites work: A new upper bound on the complexity of the all pairs shortest path problem
cites work: Worst-case update times for fully-dynamic all-pairs shortest paths
cites work: Algorithm Theory - SWAT 2004
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
DOI: 10.1016/J.DAM.2011.02.007
description: scientific article; zbMATH DE number 5964713