TITLE: Space-Efficiency for Routing Schemes of Stretch Factor Three AUTHORS: Cyril Gavoille and Marc Gengler ABSTRACT: We deal with deterministic distributed routing algorithms on arbitrary n-node networks. We want to minimize, for each router, the amount of routing information that needs to be stored in order to implement the local routing algorithm, even if the names of the routers can be chosen in advance. We take also into account the length of the routing paths and consider the stretch factor which is the maximum ratio between the length of the paths computed by the routing algorithm and the distance between the source and the destination. We show that there exists an n-node network on which every routing algorithm of stretch factor s < 3 requires at least a total of Omega(n2) bits of routing information. We show a similar result for networks of diameter 2.