zbMATH — the first resource for mathematics

Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs. (English) Zbl 0906.05067
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)\).
Reviewer: H.Müller (Jena)

05C85 Graph algorithms (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI Link
[1] Ahuja, R; Magnanti, T.L; Orlin, J.B, Network flows, theory, algorithms and applications, (1993), Prentice-Hall, Englewood Cliffs, NJ · Zbl 1201.90001
[2] Amilhastre, J; Vilarem, M.C; Janssen, P, Complexity of minimum biclique cover and decomposition for a class of bipartite graphs, () · Zbl 0906.05067
[3] Bordat, J.P, Calcul pratique du treillis de Galois d’une correspondance, Math. sci. hum., 96, 31-47, (1986) · Zbl 0626.06007
[4] Brandstädt, A, Special graph classes —a survey, ()
[5] Fishburn, P.C; Hammer, P.L, Bipartite dimensions and bipartite degrees of graphs, (), Available at · Zbl 0861.05035
[6] Franzblau, D.S; Kleitman, D.J, An algorithm for covering polygons with rectangles, Inform. control, 63, 164-189, (1984) · Zbl 0591.68073
[7] Froidure, V, Rangs des relations binaires, semigroupes de relations non ambigues, () · Zbl 0873.20044
[8] M. Habib, L. Nourine, A new lattice-based heuristic for taxonomy encoding, Private communication 1996.
[9] Jiang, Tao; Ravikumar, B, Minimal NFA problems are hard, SIAM J. comput., 22, 1117-1141, (1993) · Zbl 0799.68079
[10] Kloks, T; Kratsch, D, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, Inform. process. lett., 55, 11-16, (1995) · Zbl 0875.68458
[11] Kratzke, T; Reznick, B; West, D, Eigensharp graphs: decomposition into complete bipartite subgraphs, Trans. amer. math. soc., 308, 2, 637-653, (1988) · Zbl 0652.05037
[12] Lubiw, A, The Boolean basis problem and how to cover some polygons by rectangles, SIAM J. discrete math., 3, 1, 98-115, (1990) · Zbl 0689.68096
[13] Lubiw, A, A weighted MIN-MAX relation for intervals, J. combin. theory, 53, 2, 151-172, (1991) · Zbl 0758.05003
[14] Müller, H, Alternating cycle-free matchings, Order, 7, 11-21, (1990) · Zbl 0805.68091
[15] Müller, H, On edge perfectness and classes of bipartite graphs, Discrete math., 149, 159-187, (1996) · Zbl 0844.68095
[16] Nau, D.S; Markowsky, G; Woodbury, M.A; Amos, D.B, A mathematical analysis of human leukocyte antigen serology, Math. biosci., 40, 243-270, (1978) · Zbl 0394.92007
[17] Orlin, J, Containment in graph theory: covering graphs with cliques, Nederl. akad. wetensch. indag. math., 39, 211-218, (1977)
[18] Wille, R, Restructuring lattice theory: an approach based on hierarchies of contexts, (), 445-470
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.