The Densest $k$-Subhypergraph Problem
From MaRDI portal
Publication:3174693
DOI10.1137/16M1096402zbMath1397.68139OpenAlexW2963725737MaRDI QIDQ3174693
George Rabanca, Eden Chlamtáč, Christian Konrad, Michael Dinitz, Guy Kortsarz
Publication date: 18 July 2018
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1096402
Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (7)
Siting renewable power generation assets with combinatorial optimisation ⋮ The maximum exposure problem ⋮ Test dense subgraphs in sparse uniform hypergraph ⋮ Sharp detection boundaries on testing dense subhypergraph ⋮ The Small Set Vertex expansion problem ⋮ Breaking thermaxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem ⋮ Approximation algorithm for minimum partial multi-cover under a geometric setting
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Public-key cryptography from different assumptions
- Detecting high log-densities
- Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
- New Tools for Graph Coloring
- Relations between average case complexity and approximation complexity
- Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
- The Densest k-Subhypergraph Problem
- Approximation Algorithms and Hardness of the k -Route Cut Problem
- Approximating Semi-matchings in Streaming and in Two-Party Communication
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Approximating Steiner Networks with Node-Weights
- Pseudorandom Generators with Long Stretch and Low Locality from Random Local One-Way Functions
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
This page was built for publication: The Densest $k$-Subhypergraph Problem
