A constant approximation algorithm for the densest k-subgraph problem on chordal graphs
From MaRDI portal
Publication:963469
DOI10.1016/J.IPL.2008.03.016zbMATH Open1185.05136OpenAlexW2021294212MaRDI QIDQ963469FDOQ963469
V. Zissimopoulos, Maria Liazi, Ioannis Milis
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
Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Clustering and domination in perfect graphs
- \(k\)-edge subgraph problems
- Incidence matrices and interval graphs
- Greedily Finding a Dense Subgraph
- The dense \(k\)-subgraph problem
- On rigid circuit graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The quadratic 0-1 knapsack problem with series-parallel support
- Heuristic and Special Case Algorithms for Dispersion Problems
- Approximation algorithms for maximum dispersion
- Efficient Optimization of Monotonic Functions on Trees
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
Cited In (15)
- Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem
- Finding connected \(k\)-subgraphs with high density
- Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
- PTAS for densest \(k\)-subgraph in interval graphs
- Largest Chordal and Interval Subgraphs Faster Than 2 n
- Numerical study of semidefinite bounds for the \(k\)-cluster problem
- Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs
- On the \(k\)-edge-incident subgraph problem and its variants
- Finding Connected Dense $$k$$-Subgraphs
- A deterministic approximation algorithm for the densest \(k\)-subgraph problem
- A polyhedral study of the maximum edge subgraph problem
- Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
- A polynomial algorithm for the k-cluster problem on the interval graphs
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Solving \(k\)-cluster problems to optimality with semidefinite programming
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)
