Abstract: Wavelength converters in optical WDM networks simplify the wavelength assignment problem in the design of virtual topologies and increase the utilization of the fiber bandwidth. However, converters are costly, and minimizing the number of converters needed to support a given level of functionality has been investigated in the literature in various contexts. In particular, previous work has addressed the problem of minimizing the number of converters needed to support broadcast over all network nodes with a given set of residual wavelengths on each link. In this talk, we show that the problem is in fact NP-Complete, but becomes tractable in the special case when the network graph is a tree. Finally, we provide some heuristic approaches to solve the general problem and measure the performance of these heuristics on various classes of networks.

Short Bio: Prashant Iyer is a PhD student in the Computer Science Dept. at North Carolina State University. He completed his MS from NCSU in May 2003 with a thesis on the complexity of traffic grooming in optical WDM path networks under Prof. Carla Savage. From June 2003 to July 2005, he was working as a software engineer for Yahoo! Inc in Bangalore, India. His current research interests include computational complexity and design of algorithms for problems in combinatorial enumeration.