Maximum bandwidth broadcast in single and multi-interface networks

A maximum bandwidth broadcast problem in multi-interface networks is considered, where each transmission, simultaneously serving a group of nodes, achieves a total bandwidth equal to the product between the smallest node bandwidth in the group and the cardinality of the group. Two variants of the problem are studied, called the K-Maximum Bandwidth Broadcast in Single-Interface Networks (MBB) and K-Maximum Bandwidth Broadcast in Multiple-Interface Networks (MBBM) problems. It is shown that the former problem can be optimally solved in polynomial time, while the latter one is computationally intractable (i.e. NP-hard). Polynomial time algorithms are devised for optimally solving some particular cases of MBBM where a common order holds and the number of used interfaces is polylogarithmic in the number of nodes.