Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
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.
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
Alfonso P. Cardenas, Larry F. Bowman, et al.
ACM Annual Conference 1975
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Alessandro Morari, Roberto Gioiosa, et al.
IPDPS 2011