Maximum Edge Bicliques in Tree Convex Bipartite Graphs
DOI10.1007/978-3-319-59605-1_5zbMath1489.68186OpenAlexW2619628459MaRDI QIDQ4632202
Publication date: 26 April 2019
Published in: Frontiers in Algorithmics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-59605-1_5
NP-completenesspolynomial timestar-convex bipartite graphsmaximum edge bicliquetree-convex bipartite graphstriad-convex bipartite graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Cites Work
- Circular convex bipartite graphs: feedback vertex sets
- Complexity of domination, Hamiltonicity and treewidth for tree convex bipartite graphs
- Feedback vertex sets on restricted bipartite graphs
- Solving the maximum edge biclique packing problem on unbalanced bipartite graphs
- Generating bicliques of a graph in lexicographic order
- Consensus algorithms for the generation of all maximal bicliques
- A continuous characterization of the maximum-edge biclique problem
- Enumeration aspects of maximal cliques and bicliques
- Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
- The maximum edge biclique problem is NP-complete
- Finding maximum edge bicliques in convex bipartite graphs
- Tractable connected domination for restricted bipartite graphs
- On Bipartite and Multipartite Clique Problems
- Circular Convex Bipartite Graphs: Feedback Vertex Set
- Independent Domination on Tree Convex Bipartite Graphs
- Two Hardness Results on Feedback Vertex Sets
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Feedback Vertex Sets on Tree Convex Bipartite Graphs
- Tree Convex Bipartite Graphs: $\mathcal{NP}$ -Complete Domination, Hamiltonicity and Treewidth
- Union Closed Tree Convex Sets
- Relations between average case complexity and approximation complexity
- Graph Classes: A Survey
- Tractable Connected Domination for Restricted Bipartite Graphs (Extended Abstract)
- Domination in Some Subclasses of Bipartite Graphs
- Tractable Feedback Vertex Sets in Restricted Bipartite Graphs
- Restricted Bipartite Graphs: Comparison and Hardness Results
- Independent Domination: Reductions from Circular- and Triad-Convex Bipartite Graphs to Convex Bipartite Graphs
- Set Cover, Set Packing and Hitting Set for Tree Convex and Tree-Like Set Systems
- Maximum matching in a convex bipartite graph
- Algorithms and Computation
- On the generation of bicliques of a graph
