The Forwarding Indices of Graphs -- a Survey <s> Difficulty of Determining the Forwarding Indices <s> A generalization of the cube-connected cycles of Preparata and Vuillemin is described which retains the symmetry of these architectures while allowing for constructions of greater density and of arbitrary degree. These constructions are of a type known as Cayley graphs, and their analysis is greatly facilitated by the applicability of methods from abstract algebra. <s> BIB001 </s> The Forwarding Indices of Graphs -- a Survey <s> Difficulty of Determining the Forwarding Indices <s> For a given graph G of order n, a routing R is a set of n(n − 1) elementary paths specified for every ordered pair of vertices in G. The edge forwarding index of a network (G,R), denoted π(G,R) is the maximum number of paths of R going through any edge e of G. The edge forwarding index of G, denoted π(G), is the minimum of π(G,R) taken over all the possible routings R of G. Given n ≤ 15 and Δ ≤ n − 1 we determine πΔ,n, the minimum of π(G) taken over all graphs G of order n with maximum degree at most Δ. This is known as the edge forwarding index problem. © 1993 by John Wiley & Sons, Inc. <s> BIB002 </s> The Forwarding Indices of Graphs -- a Survey <s> Difficulty of Determining the Forwarding Indices <s> An n-dimensional crossed cube, CQ/sub n/, is a variation of hypercubes. In this paper, we give a new shortest path routing algorithm based on a new distance measure defined herein. In comparison with Efe's algorithm, which generates one shortest path in O(n/sup 2/) time, our algorithm can generate more shortest paths in O(n) time. Based on a given shortest path routing algorithm, we consider a new performance measure of interconnection networks called edge congestion. Using our shortest path routing algorithm and assuming that message exchange between all pairs of vertices is equally probable, we show that the edge congestion of crossed cubes is the same as that of hypercubes. Using the result of edge congestion, we can show that the bisection width of crossed cubes is 2/sup n-1/. We also prove that wide diameter and fault diameter are [n/2]+2. Furthermore, we study embedding of cycles in cross cubes and construct more types than previous work of cycles of length at least four. <s> BIB003
As we have stated in Subsection 2.1, the problem of computing the forwarding indices of a general graph is an NP-complete problem. Also, for a given graph G, determining its forwarding indices ξ(G) and π(G) is also very difficult. The first difficulty is designing a routing R such that ξ x (G, R) for any x ∈ V (G) or π x (G, R) for any e ∈ E(G) can be conveniently computed. An ideal routing can be found by the current algorithms for finding shortest paths. However, in general, it is not always the case that the forwarding indices of a graph can be obtained by a minimum routing. For example, consider the wheel W 7 of order seven. The hub x, other vertices 0, 1, · · · , 5. A minimum and bidirectional routing R m is defined as follows. Thus, we have ξ(W 7 , R m ) = 6. However, if we define a routing R that is the same as the minimum routing R m except for R(2, 5) = (2, 1, 0, 5), R(5, 2) = BIB003 BIB001  BIB002 . Then the routing R is not minimum. We have Thus, we have ξ(W 7 , R) = 4 < 6 = ξ(W 7 , R m ). The second difficulty is that the forwarding indices are always attained by a bidirectional routing. For example, for the hypercube Q n (n ≥ 2), ξ(Q n ) = n2 n−1 − (2 n − 1) = 2 n−1 (n−2)+1. Since 2 n−1 (n−2)+1 is odd, ξ(Q n ) can not be attained by a bidirectional routing.