On the construction of communication networks satisfying bounded fan-in of service ports

The problem of minimizing the number of service ports of a central facility which serves a number of users subject to some constraints is addressed. At any time, a set of at most s users may want to use the facility, and one user can be connected to each port at a given time. It is assumed that there are direct communication links from users to service ports, with at most d links incident at a single service port. This problem maps to the graph-theoretic problem of minimizing the number of outputs of a bipartite graph with n inputs, such the degree of each output node is at most d and every set of k⩽s inputs is joined collectively to at least k different outputs. This minimum is denoted by f (n, s, d). A linear programming formulation is also given