The maximum edge biclique problem is NP-complete

Cites Work

Title not available (Why is that?)
On the Shannon capacity of a graph
Node-and edge-deletion NP-complete problems
Approximating Clique and Biclique Problems
The NP-completeness column: An ongoing guide
Bipartite sandwiches: Semidefinite relaxations for maximum biclique
Bicliques and eigenvalues

Cited In (74)

On computing large temporal (unilateral) connected components
Fractional minimal rank
A linear programming formulation for the maximum complete multipartite subgraph problem
Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth
\(k\)-partite cliques of protein interactions: a novel subgraph topology for functional coherence analysis on PPI networks
On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
Scale reduction techniques for computing maximum induced bicliques
On computing large temporal (unilateral) connected components
On the generation of bicliques of a graph
Computing dense and sparse subgraphs of weakly closed graphs
Title not available (Why is that?)
Combinatorics and algorithms for quasi-chain graphs
Combinatorics and algorithms for quasi-chain graphs
Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
Reducing Rank of the Adjacency Matrix by Graph Modification
Topological Bounds for Graph Representations over Any Field
On Independent Sets and Bicliques in Graphs
Spike-and-slab Lasso biclustering
Summarizing transactional databases with overlapped hyperrectangles
Title not available (Why is that?)
Chromatic characterization of biclique covers
Biclique-Helly graphs
Graph-Based Data Clustering with Overlaps
Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
A simple filter for detecting low-rank submatrices
Graph-based data clustering with overlaps
Parameterized algorithms for edge biclique and related problems
Maximum Edge Bicliques in Tree Convex Bipartite Graphs
Parameterized Algorithms for Maximum Edge Biclique and Related Problems
Multiple phase tabu search for bipartite Boolean quadratic programming with partitioned variables
Coherent network partitions: characterizations with cographs and prime graphs
Subclasses of circular-arc bigraphs: Helly, normal and proper
The biclique \(k\)-clustering problem in bipartite graphs and its application in bioinformatics
Bicolored independent sets and bicliques
A note on a maximum \(k\)-subset intersection problem
Finding biclusters by random projections
Rank reduction of oriented graphs by vertex and edge deletions
Inapproximability of Maximum Weighted Edge Biclique and Its Applications
Title not available (Why is that?)
Generating bicliques of a graph in lexicographic order
Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
Consensus algorithms for the generation of all maximal bicliques
On the generation of bicliques of a graph
On the geometric interpretation of the nonnegative rank
Multi-objective evolutionary biclustering of gene expression data
Coherent network partitions
Using underapproximations for sparse nonnegative matrix factorization
Biclique graphs and biclique matrices
Clique problem, cutting plane proofs and communication complexity
On the inapproximability of maximum intersection problems
Title not available (Why is that?)
A continuous characterization of the maximum-edge biclique problem
Bi-objective optimization of biclustering with binary data
A notion of cross-perfect bipartite graphs
Complexity of modification problems for reciprocal best match graphs
Exact exponential-time algorithms for finding bicliques
Identifying critical nodes in undirected graphs: complexity results and polynomial algorithms for the case of bounded treewidth
Reducing rank of the adjacency matrix by graph modification
Maximal-sum submatrix search using a hybrid constraint programming/linear programming approach
On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
Finding maximum edge bicliques in convex bipartite graphs
Mixed Integer Programming for Searching Maximum Quasi-Bicliques
Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
Algorithms for induced biclique optimization problems
The Bipartite QUBO
Management and analysis of DNA microarray data by using weighted trees
A convexity upper bound for the number of maximal bicliques of a bipartite graph
Nuclear norm minimization for the planted clique and biclique problems
Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
Partition of a binary matrix into \(k\) (\(k \geq 3\)) exclusive row and column submatrices is difficult
Biclique completion problems for multicast network design
Finding preferred subsets of Pareto optimal solutions
On independent sets and bicliques in graphs
Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

This page was built for publication: The maximum edge biclique problem is NP-complete

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