𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Lower bounds for linear interval routing

✍ Scribed by Eilam, T.; Moran, S.; Zaks, S.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
211 KB
Volume
34
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Linear interval routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an interval with no wraparound. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For interval routing, the upper bound and lower bound on this quantity are 2D and 2D Οͺ 3, respectively, where D is the diameter of the network. We prove a lower bound of ⍀(D 2 ) on the length of a path a message traverses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the total 2 -diameter (defined in Section 4) of the network, and by presenting a family of graphs for which this lower bound is tight.

πŸ“œ SIMILAR VOLUMES

A lower bound for interval routing in ge
A lower bound for interval routing in general networks
✍ Tse, Savio S. H.; Lau, Francis C. M. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 109 KB πŸ‘ 2 views

Interval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of t

Guaranteed recursive non-linear state bo
Guaranteed recursive non-linear state bounding using interval analysis
✍ Michel Kieffer; Luc Jaulin; Γ‰ric Walter πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 241 KB

## Abstract The problem considered here is state estimation in the presence of unknown but bounded state perturbations and measurement noise. In this context, most available results are for linear models, and the purpose of the present paper is to deal with the non‐linear case. Based on interval an

Upper and lower bounds for local electro
Upper and lower bounds for local electromagnetic quantities
✍ R. Albanese; R. Fresa πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 155 KB πŸ‘ 1 views

Most engineering problems are solved by means of numerical methods that are able to provide only approximate solutions, for which it would be extremely useful to have efficient error estimators. Upper and lower bounds for quantities of integral character, like the stored magnetic energy or the ohmi