The maximum edge biclique problem is NP-complete

Untitled work

(1979) · Cited by 43,841

On the Shannon capacity of a graph

Lovász, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,658

The NP-completeness column: An ongoing guide

Johnson, D. S. (1986) · Journal of Algorithms · doi:10.1016/0196-6774(86)90020-9 · Cited by 799

Node-and edge-deletion NP-complete problems

Yannakakis, M. (1978) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/800133.804355 · Cited by 445

Approximating Clique and Biclique Problems

Hochbaum, D. S. (1998) · Journal of Algorithms · doi:10.1006/jagm.1998.0964 · Cited by 113

The NP-completeness column: An ongoing guide

Johnson, D. S. (1987) · Journal of Algorithms · doi:10.1016/0196-6774(87)90021-6 · Cited by 75

Bicliques and Eigenvalues

Haemers, W. H. (2001) · Journal of Combinatorial Theory Series B · doi:10.1006/jctb.2000.2020 · Cited by 20

Bipartite sandwiches: bounding the size of a maximum bicliquePreprint

Ṗasechnik, D. V. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.math/9907109 · Cited by 3

Bipartite sandwiches: semide?nite relaxations for maximum biclique

Ṗasechnik, D. V. (1999) · Electronic Notes in Discrete Mathematics · doi:10.1016/s1571-0653(05)80046-0 · Cited by 2

Assisted design and analysis of attack trees

Audinot, M. (2018) · doi:10.70675/9ddbcfafzc957z4327z854ez97c7169eb7f9 · Cited by 3

Identifying the largest complete data set from ALFRED

Uduman, M. (2006) · RIT Scholar Works (Rochester Institute of Technology) · Cited by 1

On Scheduling Mesh-Structured Computations on Unreliable Computers on the Internet

Gao, L. (2012)

The Two Bicliques Problem is in NP intersection coNPPreprint

Shalu, M. A., & Vijayakumar, S. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1104.3463

Mining Subspace Clusters from Distributed Data

Bian, H., & Bhatnagar, R. (2009) · Studies in computational intelligence · doi:10.1007/978-3-642-01209-9_7

Mining Protein Interaction Groups

Wang, L. (2012) · IntechOpen eBooks · doi:10.5772/38293

Resource allocation in selfish and cooperative distributed systems

Skowron, P. (2014)

Max-variance Clustering and Biclustering of Microarray Data

Cano, C., Blanco, S., García, F., & Blanco, A. J. (2008)

An Algorithm for Mining Weighted Dense Maximal 1-Complete Regions

Bian, H., & Bhatnagar, R. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-78488-3_2

Inapproximability of Maximum Weighted Edge Biclique via Randomized Reduction and Its ApplicationsPreprint

Tan, J. (2007) · arXiv (Cornell University)

Empacotamento de bicliques em grafos bipartidos

Freire, A. D. S. (2012) · doi:10.11606/t.45.2012.tde-26112012-161435

Optimisation algorithms for microarray biclustering

Perrin, D., & Duhamel, C. D. (2013) · Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) · doi:10.1109/embc.2013.6609569

Partition of a Binary Matrix into k (k ≥ 3) Exclusive Row and Column Submatrices Is Difficult

Liu, P., Zhu, D., Xiao, J., Xie, Q., & Mao, Y. (2014) · Mathematical Problems in Engineering · doi:10.1155/2014/934630

An Exact Algorithm for 3-Biclique Vertex Partition

Liu, P. Q., Zhu, D. M., Xie, Q. S., & Xiao, J. J. (2010) · Applied Mechanics and Materials · doi:10.4028/www.scientific.net/amm.40-41.189

Clique problem, cutting plane proofs and communication complexity

Jukna, S. P. (2012) · Information Processing Letters · doi:10.1016/j.ipl.2012.07.003

Minimum‐weight subgraphs with unicyclic components and a lower‐bounded girth

Ben‐Ameur, W., Hadji, M., & Ouorou, A. (2013) · Networks · doi:10.1002/net.21487

Mining massive SNP data for identifying associated SNPs and uncovering gene relationships

Webb, A., Albin, A., Ye, Z., Rastegar-Mojarad, M., Huang, K., Parvin, J. D., Sadée, W., Li, L., Lin, S. M., & Xiang, Y. (2014) · ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM-BCB) · doi:10.1145/2649387.2649395

Removal of Mirror Bicliques from a Symmetric Matrix

Savio, M. R. D., Sankar, A., & Nataraj, R. V. (2014) · International Conference on Interdisciplinary Advances in Applied Computing (ICONIAAC) · doi:10.1145/2660859.2660955

Binary factorization compression and Consensus algorithm

Fu, Y., Chen, W., & Fu, D. (2009) · Journal of Computer Applications · doi:10.3724/sp.j.1087.2009.02703

Risk haplotype pattern discovery for gene mapping by recursive partitioning method based on weighted classification trees

Tran, T., & Minh, H. N. (2010) · International Journal of Computational Intelligence in Bioinformatics and Systems Biology · doi:10.1504/ijcibsb.2010.031389

An Exact Algorithm for Finding K-Biclique Vertex Partitions of Bipartites

Liu, P. Q. (2013) · Advanced materials research · doi:10.4028/www.scientific.net/amr.710.687

Algorithmic and Complexity Issues of Three Clustering Methods in Microarray Data Analysis

Tan, J., Chua, K. S., & Zhang, L. (2005) · Lecture notes in computer science · doi:10.1007/11533719_10

SECURING WIRELESS BROADCAST COMMUNICATIONS AGAINST INTERNAL ATTACKS

Liu, S. (2012) · UA Campus Repository (The University of Arizona)

An exact algorithm for finding k-biclique vertex partitions of bipartites

Liu, P. (2012) · International Conference on Applied Robotics for the Power Industry (CARPI) · doi:10.1109/carpi.2012.6356376

Signal Processing Algorithms and Their Applications

Preserve, L. (2011)

A priori assessment of data quality in molecular

Meusemann, K., von Reumont, B. M., Kück, P., & Prohaska, S. J. (2014)

O problema da máxima interseção de k-subconjuntos

Bogue, E. T. (2014) · doi:10.47749/t/unicamp.2014.931530

Identification of Shifting Regulatory Modules in Time Series Gene Expression Data Using a Linear Time Biclustering Algorithm

Phukhachee, T., & Maneewongvatana, S. (2013) · International Journal of Bioscience Biochemistry and Bioinformatics · doi:10.7763/ijbbb.2013.v3.200

OPTIMIZATION-BASED NETWORK ANALYSIS WITH APPLICATIONS IN CLUSTERING AND DATA MINING A Dissertation

Shahinpour, S. (2013)

The Quorum Deployment Problem (Extended Abstract)

Gilbert, S. L., & Malewicz, G. G. (2005)

Multipartite graph clustering for structured datasets and automating ortholog extraction

Kulikowski, C. A., & Vashist, A. (2006)

On the Phase Transition of Finding a Biclique in a larger Bipartite GraphPreprint

Alonso, R., Monroy, R., & Aguirre, E. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1609.05876

Internet Computing of Tasks with Dependencies Using Unreliable Workers (Extended Abstract)

Gao, L., & Malewicz, G. G. (2005)

A Sparse Coding Method for Specification Mining and Error Localization

Li, W., & Seshia, S. A. (2011) · UC Berkeley

Bi-(N-) cluster editing and its biomedical applications

Sun, P. G. (2016) · MPG.PuRe (Max Planck Society) · doi:10.22028/d291-26781

Information analysis to study interactions between different genes and diseases

Nahar, K. M. O., & Alsmadi, I. M. (2017) · doi:10.1109/icitech.2017.8079907

Biagrupamento heurístico e coagrupamento baseado em fatoração de matrizes: um estudo em dados textuais

Diaz, A. K. R. (2018) · doi:10.11606/d.100.2018.tde-12112018-182428

Policy-Compliant Path Diversity and Bisection BandwidthPreprint

Klöti, R., Kotronis, V., Ager, B., & Dimitropoulos, X. A. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1611.02842

Spatiotemporal subspace feature tracking by mining discriminatory characteristics

Appiah, R. D. (2017)

Framework para classificação das mutações de vírus HIV

Ozahata, M. C. (2019) · doi:10.11606/d.95.2019.tde-28072019-161718

Mutex Graphs and Multicliques: Reducing Grounding Size for Planning

Spies, D., You, J.-H., & Hayward, R. (2019) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.306.20

DeMoS: Dense Module based Gene Signature Detection through Quasi-Clique: An Application to Cervical Cancer PrognosisPreprint

Saha, S. G., Mallik, S., & Bandyopadhyay, S. (2020) · doi:10.21203/rs.3.rs-17212/v1

Combinatorics and Algorithms for Quasi-Chain Graphs

Alecu, B., Atminas, A., Lozin, V., & Malyshev, D. S. (2022) · Algorithmica · doi:10.1007/s00453-022-01019-6

Minimizing Annotation Effort via Max-Volume Spectral Sampling

Quattoni, A., & Carreras, X. (2021) · Findings of the Association for Computational Linguistics: EMNLP (Findings of EMNLP) · doi:10.18653/v1/2021.findings-emnlp.246

Facets of the Total Matching Polytope for bipartite graphsPreprint

Ferrarini, L. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2111.15528

Introduction

Fang, Y., Wang, K., Lin, X., & Zhang, W. (2022) · SpringerBriefs in computer science · doi:10.1007/978-3-030-97568-5_1

CSS on Bipartite Networks

Fang, Y., Wang, K., Lin, X., & Zhang, W. (2022) · SpringerBriefs in computer science · doi:10.1007/978-3-030-97568-5_3

On Computing Large Temporal (Unilateral) Connected Components

Costa, I. L., Lopes, R., Marino, A., & Silva, A. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-34347-6_24

Um Algoritmo VNS para o Problema da Máxima Interseção de k Subconjuntos

Costa, J. R. D. F., Dias, F. C. S., & Tavares, W. A. (2018) · Anais do Simpósio Brasileiro de Pesquisa Operacional · doi:10.59254/sbpo-2018-85351

Algoritmo GRASP-VND para o problema da máxima biclique balanceada com peso no vértice

Assunção, L. M. A., & Pinheiro, R. G. S. (2020) · Anais do Simpósio Brasileiro de Pesquisa Operacional · doi:10.59254/sbpo-2020-124989

A Semidefinite Programming-Based Branch-and-Cut Algorithm for Biclustering

Sudoso, A. M. (2024) · INFORMS journal on computing · doi:10.1287/ijoc.2024.0683

$$(\alpha ,\beta )$$-Butterfly Computation on Bipartite Graphs

Bai, J., Zhou, J., Du, M., & Chen, Z. (2024) · Arabian Journal for Science and Engineering · doi:10.1007/s13369-024-09632-z

Exact Algorithms for the Maximum k-Balanced Weighted Biclique Problem

Liu, J., Wang, J., Feng, Q., & Shi, F. (2025) · Lecture notes in computer science · doi:10.1007/978-981-96-8312-3_9

Maximum edge bi-clique via matrix decomposition

Omer, S., & Ali, M. M. (2025) · Journal of Industrial and Management Optimization · doi:10.3934/jimo.2025131

Outcome-guided spike-and-slab Lasso Biclustering: A Novel Approach for Enhancing Biclustering Techniques for Gene Expression Analysis

Vargas-Mieles, L. A., Kirk, P., & Wallace, C. (2025) · Statistics and Computing · doi:10.1007/s11222-025-10709-4

A hybrid mapping algorithm for reconfigurable nanoarchitectures

Al-Mutairi, H. K., & Ahmad, I. (2015) · Journal of Engineering Research · doi:10.1016/s2307-1877(25)00407-9

From Bicliques to BiFlexi Cliques: A New Era of Bipartite Subgraph Discovery

Han, T., Kim, S. L., Choo, W., & Kim, J. (2025) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/3746252.3760927

Theoretically and Practically Efficient Maximum Biclique Search

Dai, Q., Li, R.-H., Qiao, L., Cui, D., & Wang, G. (2025) · Proceedings of the ACM on Management of Data · doi:10.1145/3769833

Efficient Maximum $$(\alpha ,\beta )$$-Quasi Biclique Computation on Bipartite Graphs

Liang, B., Liu, Y., Zhou, H., Xu, W., He, S., & Liu, S. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-3906-2_7

A New Algorithmic Framework for the Maximum k-Balanced Weighted Biclique ProblemPreprint

Liu, J., Zeng, X., Wang, J., Feng, Q., & Shi, F. (2026) · SSRN Electronic Journal · doi:10.2139/ssrn.6184190

Synthèse de réseaux à composantes connexes unicycliques

Hadji, M. (2009) · doi:10.70675/8c4df8b2zf5e1z425ez9320zc6be08ca07c1

A search space of graph motifs for graph compression : from Powergraphs to triplet concepts

Bourneuf, L. (2019) · theses.fr (ABES) · doi:10.70675/5360ed10zdefbz4796zba1bz3341b7546384

Contribution to solving the combinatorial optimization problems : case of the problem of K-clusters in a bipartite graph and the quadratic knapsack problem

Al-Iedani, N. H. Q. (2017) · theses.fr (ABES) · doi:10.70675/5dbe99baz3f0az4ca4za548z1b9146b3f525

Evaluation of the use of public toxicological data for chemical hazard prediction through computational methods

Grenet, I. (2019) · theses.fr (ABES) · doi:10.70675/a6af77b4z321dz4ab5z8b89zb2a887c44ddc

Printed image multiplexing by laser processing and its application to security and identity documents

Dalloz, N. (2022) · doi:10.70675/b3ee7890z08f1z4e79z9b33zf41a2d835346

Approximation Algorithms for Channel Coding and Non-signaling Correlations

Fermé, P. (2023) · doi:10.70675/a2424b04z59cdz40bazaa39zcfaa14e86171

Algorithmic and theoretical aspects of sparse deep neural networks

Le, Q.-T. (2023) · theses.fr (ABES) · doi:10.70675/01b91cd8zefbaz442az9887zbfcec3e1132f

Efficient Error Setting for Subspace Miners

Shaham, E., Sarne, D., & Moshe, B. B. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-08979-9_1

SQAC: Scalable Querying of Attribute-Constrained (α, β)-Cores over Large Bipartite Graphs

Deng, X., Peng, P., Sun, B., Dai, S., Qin, Z., & Chang, L. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00189

Exploring $(\alpha-p, \beta)$-Cores in Bipartite Social Graphs

Wu, C., Wu, J., Wan, W., & Xu, J. (2026) · International Conference on Artificial Intelligence and Big Data (ICAIBD) · doi:10.1109/icaibd69640.2026.11637156

Maximum Defective Biclique Search in Large Bipartite Graphs

Cui, D., Li, R.-H., Dai, Q., Qin, H., & Wang, G. (2026) · Proceedings of the VLDB Endowment · doi:10.14778/3836663.3836687

Designing and adapting dropshipping virtual distribution networks

Cassidey, T. B., Griffin, E. C., Keskin, B. B., & Satici, O. (2026) · European Journal of Operational Research · doi:10.1016/j.ejor.2026.10.015

Using associative networks for document categorization

Bloom, N. (2015) · doi:10.3990/1.9789036538787

Identification of K-Tolerance Regulatory Modules in Time Series Gene Expression Data Using a Biclustering Algorithm

Phukhachee, T., & Maneewongvatana, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-02750-0_15

Finding Maximum Edge Biclique in Bipartite Networks by Integer Programming

Sözdinler, M., & Özturan, C. (2018) · IEEE International Conference on Computational Science and Engineering (CSE) · doi:10.1109/cse.2018.00025 · Cited by 15

Maximum Edge Bicliques in Tree Convex Bipartite Graphs

Chen, H., & Liu, T. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59605-1_5 · Cited by 6

On bipartite and multipartite . . .

Dawande, M., Keskinocak, P., Swaminathan, J. M., & Tayur, S. (2000)

Finding Maximum Edge Bicliques in Convex Bipartite Graphs

NussbaumDoron, PuShuye, SackJörg-Rüdiger, UnoTakeaki, & Zarrabi-ZadehHamid (2012) · Algorithmica · doi:10.5555/3118237.3118545 · Cited by 1

Maximizing edge-ratio is NP-complete

Noble, S. D., Hansen, P., & Mladenović, N. (2011) · Discrete Applied Mathematics · doi:10.1016/j.dam.2011.07.016 · Cited by 2