A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs

DOI10.1016/j.ipl.2008.03.016zbMath1185.05136OpenAlexW2021294212MaRDI QIDQ963469

Maria Liazi, Ioannis Milis, Vassilios Zissimopoulos

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.03.016

zbMATH Keywords

chordal graphsapproximation algorithmsdensest \(k\)-subgraph

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Numerical Study of Semidefinite Bounds for the k-cluster Problem ⋮ Finding connected \(k\)-subgraphs with high density ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs ⋮ A polynomial algorithm for the k-cluster problem on the interval graphs ⋮ Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs ⋮ PTAS for densest \(k\)-subgraph in interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Clustering and domination in perfect graphs
• \(k\)-edge subgraph problems
• Approximation algorithms for maximum dispersion
• The quadratic 0-1 knapsack problem with series-parallel support
• Incidence matrices and interval graphs
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Efficient Optimization of Monotonic Functions on Trees
• Heuristic and Special Case Algorithms for Dispersion Problems
• Greedily Finding a Dense Subgraph
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• The dense \(k\)-subgraph problem