Compact roundtrip routing with topology-independent node names
Marta Arias, Lenore Cowen, Kofi A. Laing · 2003
This paper presents compact roundtrip routing schemes with local tables of size Õ(√n) and stretch 6 for any directed network with arbitrary edge weights; and with local tables of size Õ(√−1n2/k) and stretch min((2k/2 −1)(k + √), 16k 2+ 8 k − 8), for any directed network with polynomially-sized edges, both in the topology-independent node-name model. These are the first topology-independent results that apply to routing in directed networks.