The densest k-subhypergraph problem

DOI10.1137/16M1096402zbMATH Open1397.68139OpenAlexW2963725737MaRDI QIDQ3174693FDOQ3174693

Authors: Eden Chlamtac, Michael Dinitz, Christian Konrad, George Rabanca, 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

Recommendations

• The densest \(k\)-subhypergraph problem
• The dense \(k\)-subgraph problem
• Approximating vertex cover in dense hypergraphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem

zbMATH Keywords

densenessapproximationhypergraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Hypergraphs (05C65)

Cites Work

• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Title not available (Why is that?)
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• The dense \(k\)-subgraph problem
• Public-key cryptography from different assumptions
• Pseudorandom generators with long stretch and low locality from random local one-way functions
• Title not available (Why is that?)
• The densest \(k\)-subhypergraph problem
• Approximating Steiner networks with node-weights
• Dial a ride from \(k\)-forest
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximation algorithms and hardness of the \(k\)-route cut problem
• New tools for graph coloring
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Improved approximation algorithm for Steiner \(k\)-Forest with nearly uniform weights
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion

Cited In (19)

• PTAS for Densest k-Subgraph in Interval Graphs
• Test dense subgraphs in sparse uniform hypergraph
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Approximation algorithm for minimum partial multi-cover under a geometric setting
• The maximum exposure problem
• The densest \(k\)-subhypergraph problem
• The small set vertex expansion problem
• Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Sharp detection boundaries on testing dense subhypergraph
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• On approximating partial scenario set cover
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
• Siting renewable power generation assets with combinatorial optimisation
• Heterogeneous dense subhypergraph detection
• Pattern masking for dictionary matching: theory and practice
• The density maximization problem in graphs
• Computing the \(k\) densest subgraphs of a graph

This page was built for publication: The densest \(k\)-subhypergraph problem

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