The dense k-subgraph problem

Uriel Feige; G Kortsarz; David Peleg

doi:10.1007/s004530010050

Back

Journal article

Peer reviewed

The dense k-subgraph problem

Uriel Feige, G Kortsarz and David Peleg

Algorithmica, Vol.29(3), pp.410-421

Mar/2001

DOI: https://doi.org/10.1007/s004530010050

Files and links (2)

url

https://doi.org/10.1007/s004530010050View

Published (Version of record) Restricted

url

https://ezproxy.weizmann.ac.il/login?url=http://dx.doi.org/10.1007/s004530010050View

Published (Version of record) Restricted

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(delta)), for some delta <1/3.

Details

Title: The dense k-subgraph problem
Creators: Uriel Feige (null) - 972WIS_INST___83
G Kortsarz (null)
David Peleg (null) - 972WIS_INST___83
Resource Type: Journal article
Publication Details: Algorithmica, Vol.29(3), pp.410-421; Mar/2001
Number of pages: 12
Language: English
DOI: https://doi.org/10.1007/s004530010050
Record Identifier: 993266182503596

Metrics

9 Record Views

See more details