Premium
Computation of the forwarding index via flows: A note
Author(s) -
de le Vega W. Fernandez,
Manoussakis Y.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240503
Subject(s) - heuristics , computer science , vertex (graph theory) , index (typography) , set (abstract data type) , routing (electronic design automation) , computation , flow network , flow (mathematics) , mathematical optimization , mathematics , combinatorics , algorithm , theoretical computer science , computer network , graph , world wide web , programming language , geometry
In a given network 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 network is the minimum of the largest load taken over all routings. We show that the problem of determining the value of the forwarding index (respectively, the forwarding index of shortest routings) is an instance of the multicommodity flow problem (respectively, flow with multipliers). Since many very good heuristics or approximation algorithms are known for these flow problems, it follows from our results that all of these methods can be used for calculating the forwarding index. © 1994 by John Wiley & Sons, Inc.