On the restricted forwarding index problem in communication networks

AbstractIn a communication network it is desirable that all pairs of nodes can exchange messages at the same time. But under the capacity constraints on nodes or links this desired property may not be satisfied; only some node pairs can communicate with each other while the rest have to be blocked. A natural question is what is the maximum number of node pairs that can communicate synchronously with the load restriction? In this paper, we first show that the problem is NP-complete. Then we present two approximation algorithms for the problems under the node load constraint and the link load constraint, respectively