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

DOI10.1016/J.EJOR.2013.09.027zbMATH Open1304.68210OpenAlexW1979368390WikidataQ60242777 ScholiaQ60242777MaRDI QIDQ2514764FDOQ2514764

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

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

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)

Cites Work

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

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)