On the Dilation of Interval Routing

Author: Gavoille C.

Source: Computer Journal, Volume 43, Number 3, 2000 , pp. 243-249(7)

Buy & download fulltext article:

Price: $42.29 plus tax (Refund Policy)

Abstract:

In this paper we deal with interval routing on $n$-node networks of diameter $D$. We show that, for all $n$ and $D$ such that $2 \leq D \leq \Theta(n)$, there exists a network on which every interval routing scheme with less than $\Omega(n/(D\log (n/D)))$ intervals per link has a routing path length at least $\lfloor 3D/2\rfloor-1$. It improves the lower bound on the routing path lengths for the range of a very large number of intervals. Moreover, we build a network of bounded degree, for all $n$ and $D$ such that $\Theta(\log n) \leq D \leq \Theta(n)$, on which every interval routing scheme with less than $\Omega(n/D^2)$ intervals per link has a routing path length at least $3D/2 - O(\log n)$.

Language: English

Document Type: Original article

Affiliations: 1: LaBRI, Universitè. Bordeaux I, 351, cours de la Libè.ration, 33405 Talence Cedex, France Email: gavoille@labri.u-bordeaux.fr

Publication date: 2000-01-01

More about this publication?

The Computer Journal publishes research papers in a full range of subject areas, as well as regular feature articles and occasional themed issues to enable readers to easily access information outside their direct area of research. The journal provides a complete overview of developments in the field of Computer Science.