Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem
From MaRDI portal
Publication:2514764
DOI10.1016/j.ejor.2013.09.027zbMath1304.68210OpenAlexW1979368390WikidataQ60242777 ScholiaQ60242777MaRDI QIDQ2514764
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
Operations research and management science (90B99) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Models and algorithms for network reduction, Convex Optimization for Group Feature Selection in Networked Data, Geometric clustering for the consolidation of farmland and woodland
Cites Work
- A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- Clustering and domination in perfect graphs
- Approximation algorithms for maximum dispersion
- New facets and a branch-and-cut algorithm for the weighted clique problem.
- The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
- An improved rounding method and semidefinite programming relaxation for graph partition
- Constrained minimum-\(k\)-star clustering and its application to the consolidation of farmland
- Upper bounds and exact algorithms for \(p\)-dispersion problems
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Detecting high log-densities
- Finding Dense Subgraphs with Size Bounds
- Greedily Finding a Dense Subgraph
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
- A Lagrangian relaxation approach to the edge-weighted clique problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item