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

Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Huijuan Wang, Alexander Zelikovsky

    Research output: Contribution to journalArticlepeer-review

    24 Scopus citations


    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, we suggest new two-coloring and compaction approach that simultaneously optimizes layout and phase assignment which is based on planar embedding of an associated conflict graph. We also describe additional approaches to cooptimization of layout and phase assignment for alternating PSM. Second, we give optimal and fast algorithms to minimize the number of phase conflicts that must be removed to ensure two colorability of the conflict graph. We reduce this problem to the T-join problem which asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A if u belongs to a given node subset T of a weighted graph. Third, we suggest several practical algorithms for the T-join problem. In sparse graphs, our algorithms are faster than previously known methods. Computational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithms.

    Original languageEnglish (US)
    Pages (from-to)175-187
    Number of pages13
    JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
    Issue number2
    StatePublished - 2000

    All Science Journal Classification (ASJC) codes

    • Software
    • Computer Graphics and Computer-Aided Design
    • Electrical and Electronic Engineering


    Dive into the research topics of 'Optimal phase conflict removal for layout of dark field alternating phase shifting masks'. Together they form a unique fingerprint.

    Cite this