The densest \(k\)-subgraph problem on clique graphs

DOI10.1007/s10878-007-9069-1zbMath1149.90127OpenAlexW2007362596MaRDI QIDQ2426654

Maria Liazi, Fanny Pascual, Vassilios Zissimopoulos, Ioannis Milis

Publication date: 23 April 2008

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-007-9069-1

zbMATH Keywords

Dynamic programmingPolynomial time approximation schemeClique graph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (7)

Finding connected \(k\)-subgraphs with high density ⋮ Edge contraction and edge removal on iterated clique graphs ⋮ On the \(k\)-edge-incident subgraph problem and its variants ⋮ Exact algorithms for problems related to the densest \(k\)-set problem ⋮ The class of \(q\)-cliqued graphs: eigen-bi-balanced characteristic, designs, and an entomological experiment ⋮ A polyhedral study of the maximum edge subgraph problem ⋮ PTAS for densest \(k\)-subgraph in interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clustering and domination in perfect graphs
• \(k\)-edge subgraph problems
• Approximation algorithms for maximum dispersion
• An improved rounding method and semidefinite programming relaxation for graph partition
• The quadratic 0-1 knapsack problem with series-parallel support
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• 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

This page was built for publication: The densest \(k\)-subgraph problem on clique graphs