Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
DOI10.1016/S0166-218X(98)00039-0zbMATH Open0906.05067OpenAlexW2065163038MaRDI QIDQ1270816FDOQ1270816
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
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
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)
Cites Work
- Network flows. Theory, algorithms, and applications.
- A mathematical analysis of human leukocyte antigen serology
- Title not available (Why is that?)
- On edge perfectness and classes of bipartite graphs
- Minimal NFA Problems are Hard
- A weighted min-max relation for intervals
- Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
- Bipartite dimensions and bipartite degrees of graphs
- Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
- Title not available (Why is that?)
- An algorithm for covering polygons with rectangles
- Eigensharp Graphs: Decomposition into Complete Bipartite Subgraphs
- Alternating cycle-free matchings
- The Boolean Basis Problem and How to Cover Some Polygons by Rectangles
- Ranks of binary relations
Cited In (33)
- On biclique covering number of the Cartesian product of graphs
- On Independent Sets and Bicliques in Graphs
- An overview of graph covering and partitioning
- On the Galois lattice of bipartite distance hereditary 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
- On independent sets and bicliques in graphs
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)
