Complexity of the Forwarding Index Problem
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.
- Forwarding and optical indices of a graph
- Forwarding index of cube-connected cycles
- The forwarding index of communication networks with given connectivity
- Static and dynamic low-congested interval routing schemes
- Forwarding indices of folded \(n\)-cubes
- Upper bounds for the forwarding indices of communication networks
- The forwarding index of directed networks
- Distance eigenvalues and forwarding indices of circulants
- Cube-connected circulants: bisection width, Wiener and forwarding indices
- On the restricted forwarding index problem in communication networks
- Metaheuristics for computing the forwarding index of a graph*
- Forwarding indices of consistent routings and their complexity
- Computation of the forwarding index via flows: A note
- Low-congested interval routing schemes for hypercubelike networks
- Lower bounds of forwarding indices of graph products
- Recursive cubes of rings as models for interconnection networks
- Algorithms and Computation
- Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
- Concurrent flows and packet routing in Cayley graphs (Preliminary version)
- Exact vertex forwarding index of the strong product of complete graph and cycle
- The forwarding indices of augmented cubes
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)