loading...
Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems
Nice, France April 22-April 26
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213409International Parallel and Distribute ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Luisa Gargano, Università di Salerno
Adele Anna Rescigno, Università di Salerno
Ugo Vaccaro, Università di Salerno
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.
Citation:
Luisa Gargano, Adele Anna Rescigno, Ugo Vaccaro, "Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems," ipdps, pp.223a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.