Optimal phase conflict removal for layout of dark field alternating phase shifting masks

We describe new, efficient algorithms for layout modification and phase assignment for dark field alternating-type phase-shifting masks in the single-exposure regime. We make the following contributions. First, the problem of minimizing the number of phase conflicts that must be removed to ensure 2-colorability of the conflict graph is transformed to the T-join problem. Second, we give new exact and approximate algorithms for the resulting T-join problem. The exact algorithm is linear in space and substantially faster for sparse graphs than previously known algorithms. The output of the approximate algorithm is much closer to the optimum than the algorithm suggested in [9]. These algorithms are applied within a `one-shot' phase assignment method suggested in [9] for co-optimization of layout and phase assignment for alternating phase-shifting masks. Preliminary computational experience is promising.