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

DOI10.1016/J.IPL.2008.03.016MaRDI QIDQ963469zbMATH OpenOpenAlexFDO

Authors Maria Liazi, Ioannis Milis, V. 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

approximation algorithmschordal graphsdensest \(k\)-subgraph

Mathematics Subject Classification ID

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

Recommendations

• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• The densest \(k\)-subgraph problem on clique graphs
• Densest \(k\)-subgraph approximation on intersection graphs
• The dense \(k\)-subgraph problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem

Cites work

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

Cited in

(18)

• The densest \(k\)-subgraph problem on clique graphs
• Approximating the sparsest \(k\)-subgraph in chordal graphs
• Finding Connected Dense $$k$$-Subgraphs
• Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Largest Chordal and Interval Subgraphs Faster Than 2 n
• Finding connected \(k\)-subgraphs with high density
• Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• A polynomial algorithm for the k-cluster problem on the interval graphs
• Numerical study of semidefinite bounds for the \(k\)-cluster problem
• Solving \(k\)-cluster problems to optimality with semidefinite programming
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• PTAS for densest \(k\)-subgraph in interval graphs
• Densest \(k\)-subgraph approximation on intersection graphs
• A polyhedral study of the maximum edge subgraph problem
• On the \(k\)-edge-incident subgraph problem and its variants

This page was built for publication: A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs

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