The dense k-subgraph problem

U. Feige, G. Kortsarz, D. Peleg

Research output: Contribution to journalArticlepeer-review

346 Scopus citations

Abstract

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)
Volume29
Issue number3
DOIs
StatePublished - Mar 2001
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Approximation algorithms
  • Dense subgraph

Fingerprint

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

Cite this