The densest k-subhypergraph problem

DOI10.1137/16M1096402MaRDI QIDQ3174693zbMATHOpenAlexFDO

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

zbMATH Keywords

densenessapproximationhypergraph

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(19)

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

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)