On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs

J. Comput. Syst. Sci., vol. 51, no. 3, pp. 400-403, 1995
← Back to References

Bibliographic Information

TitleOn the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs
AuthorsRaimund Seidel
VenueJ. Comput. Syst. Sci., vol. 51, no. 3, pp. 400-403
Year1995
Linkhttps://doi.org/10.1006/jcss.1995.1078

Summary

Achieves O(n^omega log n) via recursive matrix squaring. Restricted to unweighted undirected connected graphs — inapplicable to the directed, disconnected networks common in real-world applications. STRATA handles all graph types.