Normalized cuts for wavelength converter placement

Wavelength converter placement is an important aspect of optical network deployment. This problem can be related to finding a minimum sufficient set solved using bipartite graph decomposition. A major problem with bipartite graph decomposition is that the resulting partitions can be unbalanced. We use the normalized cut formulation used in computer vision to arrive at balanced partitions and a heuristic to arrive at wavelength converter placements. We calculate the resulting blocking probabilities with the converter placement obtained from our algorithm for NSFNET and EON topologies. The normalized cuts approach provides results comparable to minimum vertex cover placement at lower computational complexity. The method is also incremental in the sense that most important placement locations are identified first.