The dense k-subgraph problem

U. Feige, G. Kortsarz, D. Peleg

Research output: Contribution to journalArticlepeer-review

346 Scopus citations


This paper considers the problem of computing the dense k-vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for the problem, with approximation ratio O(nδ), for some δ < 1/3.

Original languageEnglish (US)
Pages (from-to)410-421
Number of pages12
JournalAlgorithmica (New York)
Issue number3
StatePublished - Mar 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Computer Science(all)
  • Computer Science Applications


  • Approximation algorithms
  • Dense subgraph


Dive into the research topics of 'The dense k-subgraph problem'. Together they form a unique fingerprint.

Cite this