Optimal (Randomized) Compact Routing SchemesResearch Paper
A routing scheme delivers messages in a network in which every vertex forwards a message using only the information it stores. Storing a full shortest-path table at every vertex costs words per vertex, which is too much for large networks, so compact routing trades storage for longer routes. The trade-off has been studied since the late 1980s:…