Approximation of dense- n2-subgraph and table compression problems

MaRDI QIDQ882965zbMATH OpenFDO

Authors Dachuan Xu, Jiye Han, Donglei Du

Publication date 29 May 2007

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

zbMATH Keywords

approximation algorithmsapproximation ratiogreedy algorithmrelaxationrounding

Mathematics Subject Classification ID

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

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.

Cited in

(2)

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

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)