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.

Distributing Energy Consumption in Multi-interface Series-Parallel Networks

Navarra A.
;
Mostarda L.
2019

Abstract

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.
2019
978-3-030-15034-1
978-3-030-15035-8
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1470444
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? ND
social impact