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

From MaRDI portal
Revision as of 16:18, 28 May 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
scientific article

    Statements

    Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs (English)
    0 references
    1 February 1999
    0 references
    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)\).
    0 references
    biclique
    0 references
    bipartite graph
    0 references
    biclique cover
    0 references
    bipartite domino-free graph
    0 references
    Galois lattice
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references