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.

A.A. Bertossi, A. Navarra, M.C. Pinotti (2011). Maximum bandwidth broadcast in single and multi-interface networks. NEW YORK : ACM [10.1145/1968613.1968636].

Maximum bandwidth broadcast in single and multi-interface networks

BERTOSSI, ALAN ALBERT;
2011

Abstract

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.
2011
Proceedings of the 5th International Conference on Ubiquitous Information Management and Communication
-
-
A.A. Bertossi, A. Navarra, M.C. Pinotti (2011). Maximum bandwidth broadcast in single and multi-interface networks. NEW YORK : ACM [10.1145/1968613.1968636].
A.A. Bertossi; A. Navarra; M.C. Pinotti
File in questo prodotto:
Eventuali allegati, non sono esposti

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/11585/102213
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact