Forwarding indices 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 vertices 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 ζ( G, R ) of a network ( G, R ) is the maximum number of paths of R passing through any vertex of G . The minimum of ζ( G, R ) over all possible routings of a connected graph G is denoted by ζ( G ). Similarly, the notion of the edge‐forwarding index of a network can be defined. In this paper, we prove that, in general, the vertex‐forwarding index cannot be obtained by taking the minimum of ζ( G, R ) over all possible consistent routings of G . However, this can be done for the class of Cayley graphs. We prove for a specific class of routings that the computation of ζ( G ) is NP‐complete for graphs of diameter at least 4 and is polynomial for graphs of diameter 2. Similar problems are studied for the edge‐forwarding index. © 1994 John Wiley & Sons, Inc.