Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

DOI10.1016/J.EJOR.2013.09.027MaRDI QIDQ2514764zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 3 February 2015

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2013.09.027

zbMATH Keywords

approximation algorithmsdense subgraphOR in forestry

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Operations research and management science (90B99)

Recommendations

• Greedily Finding a Dense Subgraph
• Greedily finding a dense subgraph
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• The dense \(k\)-subgraph problem
• Finding connected \(k\)-subgraphs with high density

Cites work

• scientific article; zbMATH DE number 26490 (Why is no real title available?)
• scientific article; zbMATH DE number 595499 (Why is no real title available?)
• scientific article; zbMATH DE number 2159163 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Lagrangian relaxation approach to the edge-weighted clique problem
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• An improved rounding method and semidefinite programming relaxation for graph partition
• Approximation algorithms for maximization problems arising in graph partitioning
• Approximation algorithms for maximum dispersion
• Clustering and domination in perfect graphs
• Constrained minimum-k-star clustering and its application to the consolidation of farmland
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Finding Dense Subgraphs with Size Bounds
• Greedily Finding a Dense Subgraph
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• Upper bounds and exact algorithms for \(p\)-dispersion problems

Cited in

(3)

• Convex optimization for group feature selection in networked data
• Models and algorithms for network reduction
• Geometric clustering for the consolidation of farmland and woodland

This page was built for publication: Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem

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