Qing Li, Zhigang Deng, et al.
IEEE T-MI
A bipartite graph G = (U, V, E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77-79] if there is a bijection π : {1, ..., | U |} → U such that Γ (π (1)) ⊇ Γ (π (2)) ⊇ ⋯ ⊇ Γ (π (| U |)), where Γ is a function that maps a node to its neighbors. We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G (U, V, E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G′ = (U, V, E′) (E′ = E ∪ F) is a chain graph. © 2009 Elsevier B.V. All rights reserved.
Qing Li, Zhigang Deng, et al.
IEEE T-MI
A. Gupta, R. Gross, et al.
SPIE Advances in Semiconductors and Superconductors 1990
Hans Becker, Frank Schmidt, et al.
Photomask and Next-Generation Lithography Mask Technology 2004
Sai Zeng, Angran Xiao, et al.
CAD Computer Aided Design