Skip to Main content Skip to Navigation
New interface
Reports (Research report)

Worst Case Bounds for Shortest Path Interval Routing

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 / log n). We also establish a worst case bound on bounded degree networks: for any Delta >= 3 and any n, we construct a network G' of n nodes and maximum degree Delta with IRS(G') in Omega(n/(log n)^2).
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:06:37 AM
Last modification on : Wednesday, October 26, 2022 - 8:15:44 AM


Files produced by the author(s)


  • HAL Id : hal-02101800, version 1



Cyril Gavoille, Eric Guevremont. Worst Case Bounds for Shortest Path Interval Routing. [Research Report] LIP RR-1995-02, Laboratoire de l'informatique du parallélisme. 1995, 2+23p. ⟨hal-02101800⟩



Record views


Files downloads