Computing the diameter polynomially faster than APSP

An algorithm for finding all shortest paths using N 2.81 N^{2.81} infinite-precision multiplications

G. Yuval · 1976

Earlier work this paper cites.

Efficient algorithms for shortest paths in sparse graphs

D.B. Johnson · 1977

Earlier work this paper cites.

Diameters of graphs: Old problems and new results

F.R.K Chung · 1987

Earlier work this paper cites.

Matrix multiplication via arithmetic progressions

D. Coppersmith and S. Winograd · 1990

Earlier work this paper cites.

On the All-Pairs-Shortest-Path problem in unweighted undirected graphs

R. Seidel · 1995

Earlier work this paper cites.

On the exponent of the all pairs shortest path problem

N. Alon, Z. Galil, and O. Margalit · 1997

Earlier work this paper cites.

Rectangular matrix multiplication revisited

D. Coppersmith · 1997

Cited alongside, same era.

All pairs shortest distances for graphs with small integer length edges

Z. Galil and O. Margalit · 1997

Cited alongside, same era.

Fast rectangular matrix multiplications and applications

X. Huang and V.Y. Pan · 1998

Cited alongside, same era.

Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)

D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani · 1999

Cited alongside, same era.

All pairs shortest paths in undirected graphs with integer weights

A. Shoshan and U. Zwick · 1999

Cited alongside, same era.

All Pairs Shortest Paths using bridging sets and rectangular matrix multiplication

Original

U. Zwick · 2002

Shortest Paths in Matrix Multiplication Time

P. Sankowski · 2005

Later among the works it cites.

Answering distance queries in directed graphs using fast matrix multiplication

R. Yuster and U. Zwick · 2005

Later among the works it cites.

All-pairs shortest paths for unweighted undirected graphs in o ⁡ ( m ​ n ) o(mn) time

T.M. Chan · 2006

Later among the works it cites.

More algorithms for All-Pairs Shortest Paths in weighted graphs

T.M. Chan · 2007

Later among the works it cites.

Subcubic equivalences between path, matrix, and triangle problems

V. Vassilevska Williams and R. Williams · 2010

Closest in time.