Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis
From MaRDI portal
Publication:5111410
Recommendations
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
- Hardness of bipartite expansion
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Minimizing the union: tight approximations for small set bipartite vertex expansion
- On Set Expansion Problems and the Small Set Expansion Conjecture
Cited in
(14)- On the complexity of fair house allocation
- Fast and Deterministic Approximations for k-Cut.
- Tight bounds for budgeted maximum weight independent set in bipartite and perfect graphs
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- Minimizing the union: tight approximations for small set bipartite vertex expansion
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Tight inapproximability of minimum maximal matching on bipartite graphs and related problems
- Partitioning subclasses of chordal graphs with few deletions
- LP relaxation and tree packing for minimum \(k\)-cut
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Partitioning subclasses of chordal graphs with few deletions
- Hardness of bipartite expansion
- Fast and deterministic approximations for \(k\)-cut
- Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis
This page was built for publication: Inapproximability of maximum edge biclique, maximum balanced biclique and minimum \(k\)-cut from the small set expansion hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111410)
