The dense k-subgraph problem

Authors
Feige, U Kortsarz, G Peleg, D
Citation
U. Feige et al., The dense k-subgraph problem, ALGORITHMIC, 29(3), 2001, pp. 410-421
Citations number
11
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
01784617 → ACNP
Volume
29
Issue
3
Year of publication
2001
Pages
410 - 421
Database
ISI
SICI code
0178-4617(200103)29:3<410:TDKP>2.0.ZU;2-N
Abstract
This paper considers the problem of computing the dense k-vertex subgraph o f a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O (n(delt a)), for some delta < 1/3.