loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Parallel and Distributed Processing Symposium (IPDPS'03)
Multicasting to Groups in Optical Networks and Related Combinatorial Optimization Problems
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
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.