For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The Biclique Cover Problem and the Modified Galois Lattice
Hideaki OTSUKI Tomio HIRATA
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2015/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
biqlique cover, Galois lattice, domino-free,
Full Text: PDF(417.1KB)>>
The minimum biclique cover problem is known to be NP-hard for general bipartite graphs. It can be solved in polynomial time for C4-free bipartite graphs, bipartite distance hereditary graphs and bipartite domino-free graphs. In this paper, we define the modified Galois lattice Gm(B) for a bipartite graph B and introduce the redundant parameter R(B). We show that R(B)=0 if and only if B is domino-free. Furthermore, for an input graph such that R(B)=1, we show that the minimum biclique cover problem can be solved in polynomial time.