The Forwarding Indices of Graphs -- a Survey <s> Relations to Other Topics <s> This report aims at a comprehensive survey of the literature dealing with the multicommodity flow problem. This problem arises naturally in network modelling wherever commodities, vehicles, or messages are to be shipped or transmitted from certain nodes of an underlying network to some others. Recent applications of mathematical programming techniques to traffic equilibrium problems in transportation studies as well as computer networks analysis has renewed considerable interest in this problem. This report discusses solution techniques for both linear and nonlinear flow problems. The former includes decomposition, partitioning, compact inverse methods, and primal-dual algorithms. Described is a variety of feasible direction methods for the latter. The report concludes by giving applications and computational experience for both types of problems. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Relations to Other Topics <s> For a connected graph G of order n ≥ 2 with positive Laplacian eigenvalues λ2,...,λn, let b(G) = n-1 1/λ2 + ... + 1/λn. In this note we derive bounds on some graph invariants (edge-density in cuts, isoperimetric number, mean distance, edge-forwarding index, edge connectivity, etc) in terms of b(G). <s> BIB002
To the knowledge of the author, until now one has not yet find an approximation algorithm with good performance ratio for finding routings of general graphs. However, de le Vega and Manoussakis  showed that the problem of determining the value of the forwarding index (respectively, the forwarding index of minimal 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 BIB001   , it follows from these results that all of these algorithms can be used for calculating the forwarding index. Teranishi BIB002 , Laplacian spectra and invariants of graphs.