An Omega(n^2 log n) Lower Bound to the Shortest Paths Problem

Andrew Chi-Chih Yao, David Avis, Ronald L. Rivest

Browse the full STOC paper archive.