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

DOI10.1016/S0166-218X(98)00039-0MaRDI QIDQ1270816zbMATH OpenOpenAlexFDO

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

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

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

Recommendations

• Covering graphs with few complete bipartite subgraphs
• scientific article; zbMATH DE number 5543290
• Covering Graphs with Few Complete Bipartite Subgraphs
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• Clustering minimum biclique completion of a bipartite graph

Cites work

• scientific article; zbMATH DE number 4016967 (Why is no real title available?)
• scientific article; zbMATH DE number 3771669 (Why is no real title available?)
• A mathematical analysis of human leukocyte antigen serology
• A weighted min-max relation for intervals
• Alternating cycle-free matchings
• An algorithm for covering polygons with rectangles
• Bipartite dimensions and bipartite degrees of graphs
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
• Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
• Minimal NFA Problems are Hard
• Network flows. Theory, algorithms, and applications.
• On edge perfectness and classes of bipartite graphs
• Ranks of binary relations
• The Boolean Basis Problem and How to Cover Some Polygons by Rectangles

Cited in

(33)

• On independent sets and bicliques in graphs
• On biclique covering number of the Cartesian product of graphs
• An overview of graph covering and partitioning
• On the Galois lattice of bipartite distance hereditary graphs
• On Independent Sets and Bicliques in Graphs
• Computation of the biclique partition number for graphs with specific blocks
• Efficient approximation for restricted biclique cover problems
• Chromatic characterization of biclique covers
• Walk-preserving transformation of overlapped sequence graphs into blunt sequence graphs with GetBlunted
• Algorithms for recognizing bipartite-Helly and bipartite-conformal hypergraphs
• Bicolored independent sets and bicliques
• An exact exponential time algorithm for counting bipartite cliques
• Covering graphs with few complete bipartite subgraphs
• Generating bicliques of a graph in lexicographic order
• Scale reduction techniques for computing maximum induced bicliques
• The complexity for the problems of covering of a graph with the minimum number of complete bipartite subgraphs
• On the generation of bicliques of a graph
• Covering Graphs with Few Complete 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
• Biclique graphs and biclique matrices
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• On minimally non-firm binary matrices
• Exact exponential-time algorithms for finding bicliques
• Biclique Coverings, Rectifier Networks and the Cost of ε-Removal
• Problems and invariants connected with bicliques and multicliques of graphs
• Efficient enumeration of maximal induced bicliques
• On computing the Galois lattice of bipartite distance hereditary graphs
• Representing attribute reduction and concepts in concept lattice using graphs
• Edge cover by connected bipartite subgraphs
• On the Galois Lattice of Bipartite Distance Hereditary Graphs
• Structural properties of biclique graphs and the distance formula
• Modeling combinatorial disjunctive constraints via junction trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1270816)