Shortest-Path Routing in Arbitrary Netwo
β
Friedhelm Meyer auf der Heide; Berthold VΓΆcking
π
Article
π
1999
π
Elsevier Science
π
English
β 197 KB
We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C and dilation D through an arbitrary network in Ε½ . O C q D q log N steps, with high probability. This time bound is optimal up to the additive log N, and it has previously only been reached for