Complexity of the Forwarding Index Problem

From MaRDI portal





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.











This page was built for publication: Complexity of the Forwarding Index Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3136613)