✦ LIBER ✦
Optimal routings in communication networks with linearly bounded forwarding index
✍ Scribed by Manoussakis, Yannis; Tuza, Zsolt
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 358 KB
- Volume
- 28
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
In a given graph with n vertices, a routing is defined as a set of n(n -1) routes, one route connecting each ordered pair of vertices. The load of a vertex is the number of routes going through it. The forwarding index of the graph is the minimum of the largest load taken over all routings. We construct undirected graphs with a high degree of symmetry and specified diameter, in which the load of every vertex is at most constant times the number of vertices. This gives a partial solution to a problem of Chung et al.