Complexity of the Forwarding Index Problem (Q3136613)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 425595
Language Label Description Also known as
default for all languages
No label defined
    English
    Complexity of the Forwarding Index Problem
    scientific article; zbMATH DE number 425595

      Statements

      Complexity of the Forwarding Index Problem (English)
      0 references
      0 references
      14 October 1993
      0 references
      NP-completeness
      0 references
      routing
      0 references
      network
      0 references
      forwarding index
      0 references
      The forwarding index problem is, for a given connected graph \(G\) and an integer \(k\), to find a way of connecting each ordered pair of vertices by a path so that every vertex is an internal point of at most \(k\) such paths. Such a problem arises in the implementation of algorithms on a distributed architecture, a model of distributed computation being represented by network of processors treating and forwarding synchronous messages and a physical constraint on the number of messages that can be treated by a single processor. More formally, a routing \(R\) of a graph \(G\) of order \(n\) is a set of \(n(n-1)\) elementary paths specified for all ordered pairs of vertices of \(G\). The load of a vertex \(v\) by \(R\) denoted by \(\xi(G,R,v)\) is the number of paths \(p\) of \(R\) passing through \(v\) such that \(v\) is not an end vertex of \(p\). The forwarding index \(\xi(G,R)\) of a network \((G,R)\) is the maximum load of a vertex by \(R\), i.e. \(\xi(G,R)=\max_{v \in V(G)} \xi(G,R,v)\). Now, the forwarding index of \(G\) is the minimum forwarding index of a network \((G,R)\), that is, \(\xi(G)=\min_ R\xi(G,R)\). It is proved that the forwarding index problem is NP-complete even if the diameter of the graph is 2, thereby answering a question of \textit{F. Chung}, \textit{E. Coffman}, \textit{M. Reiman} and \textit{B. Simon} [IEEE Trans. Inform. Theory, 33, 224-232 (1987; Zbl 0626.94019)] concerning the complexity of the problem.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references