Scale reduction techniques for computing maximum induced bicliques

DOI10.3390/A10040113MaRDI QIDQ2633172zbMATH OpenOpenAlexFDO

Authors Shahram Shahinpour, Shirin Shirvani, Zeynep Ertem, Sergiy Butenko

Publication date 8 May 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a10040113

zbMATH Keywords

community detectionbiclusteringcomplex networksmaximum biclique

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Deterministic network models in operations research (90B10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On problem of finding all maximal induced bicliques of hypergraph
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs
• The biclique \(k\)-clustering problem in bipartite graphs and its application in bioinformatics
• Efficient enumeration of maximal induced bicliques

Cites work

• scientific article; zbMATH DE number 5004850 (Why is no real title available?)
• scientific article; zbMATH DE number 1424314 (Why is no real title available?)
• A fast algorithm for the maximum clique problem
• A simple and faster branch-and-bound algorithm for finding a maximum clique
• Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations
• Approximating Clique and Biclique Problems
• Arboricity and bipartite subgraph listing algorithms
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs
• Consensus algorithms for the generation of all maximal bicliques
• Enumeration aspects of maximal cliques and bicliques
• Exact exponential-time algorithms for finding bicliques
• Finding maximum edge bicliques in convex bipartite graphs
• Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
• Inapproximability of Maximum Weighted Edge Biclique and Its Applications
• Maximum weight relaxed cliques and Russian doll search revisited
• Node-and edge-deletion NP-complete problems
• On bipartite and multipartite clique problems
• On clique relaxation models in network analysis
• On the power of simple reductions for the maximum independent set problem
• Parameterized algorithms for maximum edge biclique and related problems
• Parameterized algorithms
• Relaxing the uniformity and independence assumptions using the concept of fractal dimension
• Solving the maximum clique and vertex coloring problems on very large sparse networks
• Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
• The maximum edge biclique problem is NP-complete
• The parameterized complexity of \(k\)-biclique

Cited in

(5)

• Solving the maximum clique and vertex coloring problems on very large sparse networks
• The bipartite QUBO
• Towards effective exact methods for the maximum balanced biclique problem in bipartite graphs
• On problem of finding all maximal induced bicliques of hypergraph
• Highly bi-connected subgraphs for computational protein function annotation

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: Scale reduction techniques for computing maximum induced bicliques

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