G. Ramalingam
Theoretical Computer Science
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.
G. Ramalingam
Theoretical Computer Science
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
David S. Kung
DAC 1998
J.P. Locquet, J. Perret, et al.
SPIE Optical Science, Engineering, and Instrumentation 1998