Given a source node and a family D of subsets of nodes of a WDM optical network, the multicasting to groups (MG) problem is to find a set of paths from the source to at least one node in each subset in D, and an assignment of wavelengths to paths so that paths sharing an optical link are assigned different wavelengths. The goal is to minimize the total number of used wavelengths. We note that MG is closely related to several important combinatorial optimization problems. These include set cover and some useful generalizations of it, that correspond to MG when the network is a tree. From the equivalence between MG and set cover it follows that unless NP ⊂ DTIME(nlog log n), MG cannot be approximated within a logarithmic factor. On the positive side, we give polynomial time approximation algorithms for the MG problem. Our algorithm has a guaranteed approximation factor matching the non-approximability bound in case of tree networks.

Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems

GARGANO, Luisa;RESCIGNO, Adele Anna;VACCARO, Ugo
2003

Abstract

Given a source node and a family D of subsets of nodes of a WDM optical network, the multicasting to groups (MG) problem is to find a set of paths from the source to at least one node in each subset in D, and an assignment of wavelengths to paths so that paths sharing an optical link are assigned different wavelengths. The goal is to minimize the total number of used wavelengths. We note that MG is closely related to several important combinatorial optimization problems. These include set cover and some useful generalizations of it, that correspond to MG when the network is a tree. From the equivalence between MG and set cover it follows that unless NP ⊂ DTIME(nlog log n), MG cannot be approximated within a logarithmic factor. On the positive side, we give polynomial time approximation algorithms for the MG problem. Our algorithm has a guaranteed approximation factor matching the non-approximability bound in case of tree networks.
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: http://hdl.handle.net/11386/1068854
 Attenzione

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

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