Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs (Q1270816): Difference between revisions

A bipartite graph is domino-free if it does not contain a 6-cycle with exactly one chord. Bipartite domino-free graphs can be recognized in time \(O(nm)\). A biclique cover (biclique decomposition) of a graph \(G\) is a family of complete bipartite subgraphs of \(G\) whose edges cover (partition) the edge set of \(G\). The minimum cardinalities of a biclique cover and a biclique partition of \(G\) are denoted by \(\text{s-dim}(G)\) and \(\text{s-part}(G)\), respectively. For bipartite domino-free graphs both parameters coincide and can be computed in time \(O(nm)\).