TITLE:Worst Case Bounds For Shortest Path Interval Routing
AUTHORS:Cyril Gavoille and Éric Guévremont
ABSTRACT:
Consider shortest path interval routing, a popular
memory-balanced method for solving the routing problem on arbitrary
networks. Given a network G, let IRS(G) denote the
maximum number of intervals necessary to encode groups of destinations
on an edge, minimized over all shortest path interval routing schemes
on G. In this paper, we establish tight worst case bounds on
IRS(G). More precisely for any n, we construct a
network G of n nodes with IRS(G) \in
\Theta(n), thereby improving on the best known lower bound of
\Omega (n/logn). We also establish a worst case bound on
bounded degree networks: for any \Delta >= 3 and any n, we
construct a network $G_\Delta$ of n nodes and maximum degree
$\Delta$ with IRS(G_\Delta) \in
\Omega(n/(logn)2).