Premium
Forwarding indices of consistent routings and their complexity
Author(s) -
Heydemann M. C.,
Meyer J. C.,
Sotteau D.,
Opatrny J.
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240204
Subject(s) - combinatorics , vertex (graph theory) , mathematics , graph , connectivity , discrete mathematics , computer science
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.