Forwarding indices of consistent routings and their complexity
Marie-Claude Heydemann, J. C. Meyer, Dominique Sotteau, Jaroslav Opatrný · Networks · 1994
Abstract 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.