The Dense k Subgraph problem

Details The Dense k Subgraph problem The Dense k Subgraph problem

2009-12-29

arxiv.org/abs/0912.5327v2

Computer Science

Discrete Mathematics

Submitted as MSc thesis, The Open University of Israel

Scientific paper

Given a graph G = (V,E) and a parameter k, we consider the problem of finding a subset U in V of size k that maximizes the number of induced edges (DkS). We improve upon the previously best known approximation ratio for DkS, a ratio that has not seen any progress during the last decade. Specifically, we improve the approximation ratio from n^{0.32258} to n^{0.3159}. The improved ratio is obtained by studying a variant to the DkS problem in which one considers the problem of finding a subset U in V of size at most k that maximizes the number of induced edges. Finally, we study the DkS variant in which one considers the problem of finding a subset U in V of size at least k that maximizes the number of induced edges.

Affiliated with

Also associated with

No associations

Rating

The Dense k Subgraph problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Dense k Subgraph problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Dense k Subgraph problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-63062