[rr-fs] compact routing running times

[Dmitri Krioukov]

cengiz,

to finish answering your question from the rrg session on running
times, first note that all the schemes i mentioned are static, so
improving running times is not an objective. nevertheless, we can
say something conclusive, but only about scheme in [1]. its running
time, up to logarithmic factors, is ~O(n^{5/3}+n^{2/3}m), which is
~O(n^{8/3}) on dense graphs, m=O(n^2). [2] does not seem to allow
for distributed implementation since it can hardly be derandomized.
[3] and [4] are more involved.

refs:
[1] L. Cowen. Compact routing with minimum stretch. SODA 1999.
[2] M. Thorup and U. Zwick. Compact routing schemes. SPAA 2001.
[3] M. Arias, et al. Compact routing with name independence. SPAA 2003.
[4] I. Abraham, et al. Compact name-independent routing with minimum
stretch. SPAA 2004.
--
dima.
http://www.krioukov.net/~dima/