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
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101800
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:06:37 AM
Last modification on : Wednesday, May 22, 2019 - 1:32:15 AM

File

RR1995-02.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101800, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

12

Files downloads

25