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

DOI10.1016/S0166-218X(98)00039-0zbMath0906.05067OpenAlexW2065163038MaRDI QIDQ1270816

Marie-Catherine Vilarem, Philippe Janssen, Jérôme Amilhastre

Publication date: 1 February 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

bipartite graphbicliqueGalois latticebiclique coverbipartite domino-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (32)

On computing the Galois lattice of bipartite distance hereditary graphs ⋮ Chromatic characterization of biclique covers ⋮ Scale reduction techniques for computing maximum induced bicliques ⋮ An overview of graph covering and partitioning ⋮ Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs, ⋮ On Independent Sets and Bicliques in Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the Galois Lattice of Bipartite Distance Hereditary Graphs ⋮ Modeling combinatorial disjunctive constraints via junction trees ⋮ On minimally non-firm binary matrices ⋮ On independent sets and bicliques in graphs ⋮ Exact exponential-time algorithms for finding bicliques ⋮ Representing attribute reduction and concepts in concept lattice using graphs ⋮ Bicolored independent sets and bicliques ⋮ An exact exponential time algorithm for counting bipartite cliques ⋮ Edge cover by connected bipartite subgraphs ⋮ Tight lower bounds on the number of bicliques in false-twin-free graphs ⋮ Tight lower bounds on the number of bicliques in false-twin-free graphs ⋮ Unnamed Item ⋮ Efficient enumeration of maximal induced bicliques ⋮ Generating bicliques of a graph in lexicographic order ⋮ Biclique graphs and biclique matrices ⋮ Covering Graphs with Few Complete Bipartite Subgraphs ⋮ On the generation of bicliques of a graph ⋮ Covering graphs with few complete bipartite subgraphs ⋮ Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs ⋮ Efficient approximation for restricted biclique cover problems ⋮ On the Galois lattice of bipartite distance hereditary graphs ⋮ Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted

Cites Work

• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Bipartite dimensions and bipartite degrees of graphs
• A weighted min-max relation for intervals
• A mathematical analysis of human leukocyte antigen serology
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Alternating cycle-free matchings
• Ranks of binary relations
• On edge perfectness and classes of bipartite graphs
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
• An algorithm for covering polygons with rectangles
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Minimal NFA Problems are Hard
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs