Distributing Energy Consumption in Multi-interface Series-Parallel Networks

Nowadays, communication networks are composed by heterogeneous devices that can communicate by means of multiple interfaces. By choosing which interfaces to activate (switch-on) at each device, several connections might be established. That is, the devices at the endpoints of each connection share at least one active interface. This is at the basis of a new but well-investigated model referred in the literature to as Multi-Interface networks. In this paper, we consider a new variant of the original model where each device is limited to activate at most a fixed number p of its available interfaces. In particular, we consider the so-called Coverage problem. Given a network G = (V,E), nodes V represent devices, edges E represent connections that can be established. The aim is to activate at most p interfaces at each node in order to establish all the connections defined by E. A connection is established whenever the two endpoints activate one common interface. Recently, the problem has been proved to be NP-hard even for the basic case of p=2. Then, various resolution algorithms have been provided for different graph topologies. Here we keep on investigating on the case p=2 when the underlying graph represents a so-called Series-Parallel network. We provide an optimal resolution algorithm based on dynamic programming for this intriguing graph class.