FORWARDING INDEXES OF CONSISTENT ROUTINGS AND THEIR COMPLEXITY

For a given connected graph G of order n, a routing R is a set of n(n - 1) simple paths R(x, y) specified for every ordered pair (x, y) of v ertices in G. A routing R is consistent if for every vertex z on R(x, y) the paths R(x, z) and R(z, y) are induced by R(x, y). A network is defined by an ordered pair (G, R), where G is a connected graph and R is a routing of G. The vertex-forwarding index xi(G, R) of a network ( G, R) is the maximum number of paths of R passing through any vertex o f G. The minimum of xi(G, R) over all possible routings of a connected graph G is denoted by xi(G). Similarly, the notion of the edge-forwar ding index of a network can be defined. In this paper, we prove that, in general, the vertex-forwarding index cannot be obtained by taking t he minimum of xi(G, R) over all possible consistent routings of G. How ever, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of xi(G) is NP-complet e for graphs of diameter at least 4 and is polynomial for graphs of di ameter 2. Similar problems are studied for the edge-forwarding index. (C) 1994 John Wiley & Sons, Inc.