Approximation algorithm for extracting densest subgraph over matching-like constraints

DOI10.1016/J.DAM.2025.10.060MaRDI QIDQ6883352zbMATH OpenFDO

Authors Jia-Bing Wang

Publication date 16 December 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.10.060

zbMATH Keywords

approximation algorithmsdensest subgraphmatching-like constraintsminimum cutpipage rounding

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Cites work

• A combinatorial strongly polynomial algorithm for minimizing submodular functions
• A deterministic almost-linear time algorithm for minimum-cost flow
• A Fast Parametric Maximum Flow Algorithm and Applications
• A faster strongly polynomial time algorithm for submodular function minimization
• A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Complexity of finding dense subgraphs
• Dense subgraph problems with output-density conditions
• Densest subgraph: supermodularity, iterative peeling, and flow
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Discounted average degree density metric and new algorithms for the densest subgraph problem
• Finding Dense Subgraphs with Size Bounds
• Finding densest \(k\)-connected subgraphs
• Generating Sparse 2-Spanners
• Greedily Finding a Dense Subgraph
• scientific article; zbMATH DE number 1670532 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• In search of dense subgraphs: How good is greedy peeling?
• In search of the densest subgraph
• Minimum cuts and related problems
• On Finding Dense Subgraphs
• Pipage rounding: a new method of constructing algorithms with proven performance guarantee
• Properties of vertex packing and independence system polyhedra
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
• Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations
• The dense \(k\)-subgraph problem
• The densest subgraph problem with a convex/concave size function
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

This page was built for publication: Approximation algorithm for extracting densest subgraph over matching-like constraints

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