All pairs shortest paths for graphs with small integer length edges

DOI10.1006/jcss.1997.1385zbMath0877.68089OpenAlexW1970052762MaRDI QIDQ1356883

Zvi Galil, Olded Margalit

Publication date: 8 December 1997

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1997.1385

zbMATH Keywords

all pairs shortest pathsall pairs shortest distances

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models ⋮ Optimal approximation algorithms for maximum distance-bounded subgraph problems ⋮ Path Laplacian matrices: introduction and application to the analysis of consensus in networks ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs ⋮ All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time ⋮ Fully dynamic all pairs shortest paths with real edge weights ⋮ An \(\tilde{O}(m^{2}n)\) algorithm for minimum cycle basis of graphs ⋮ Small-\(m\) method for detecting all longest paths

Cites Work

• Matrix multiplication via arithmetic progressions
• On the exponent of all pairs shortest path problem
• All pairs shortest distances for graphs with small integer length edges
• Unnamed Item