An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
type: Item
instance of: scholarly article
title: An \(O(n^{3}(\log\log n /\log n )^{5/4})\) time algorithm for all pairs shortest path
zbMATH Open document ID: 1147.68092
author: Yijie Han
published in: Algorithmica
publication date: 2008-07-01T00:00:00Z
Mathematics Subject Classification ID: 68W05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5294789
zbMATH Keywords: Algorithms
zbMATH Keywords: Complexity
zbMATH Keywords: Graph algorithms
zbMATH Keywords: Shortest path
MaRDI profile type: Publication
full work available at URL: s00453-007-9063-0
OpenAlex ID: W2114365471
cites work: Q4091421
cites work: Q3948568
cites work: Improved parallel integer sorting without concurrent writing
cites work: Algorithms and Data Structures
cites work: A more efficient algorithm for the min-plus multiplication
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: All pairs shortest distances for graphs with small integer length edges
cites work: Improved algorithm for all pairs shortest paths
cites work: Q4737147
cites work: A Shortest Path Algorithm for Real-Weighted Undirected Graphs
cites work: Algorithms – ESA 2005
cites work: On the all-pairs-shortest-path problem in unweighted undirected graphs.
cites work: A new upper bound on the complexity of the all pairs shortest path problem
cites work: An \(O(n^{3}\log \log n/\log n)\) time algorithm for the all-pairs shortest path problem
cites work: Undirected single-source shortest paths with positive integer weights in linear time
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
cites work: Algorithms and Computation
DOI: 10.1007/S00453-007-9063-0
description: scientific article; zbMATH DE number 5294789