Approximation of dense- n2-subgraph and table compression problems

zbMATH Open1117.05102MaRDI QIDQ882965FDOQ882965

Authors: Dachuan Xu, Jiye Han, Donglei Du 

Publication date: 29 May 2007

Published in: Science in China. Series A (Search for Journal in Brave)

Recommendations

• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection
• The dense \(k\)-subgraph problem
• A deterministic approximation algorithm for the densest \(k\)-subgraph problem
• scientific article; zbMATH DE number 1182772
• A note on the approximability of the dense subgraph problem.

zbMATH Keywords

greedy algorithmapproximation algorithmsrelaxationroundingapproximation ratio

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Semidefinite programming (90C22) Approximation algorithms (68W25)

Cited In (2)

• Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
• Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection

This page was built for publication: Approximation of dense-\(\frac n2\)-subgraph and table compression problems

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