Finding large and small dense subgraphs

Details Finding large and small dense subgraphs Finding large and small dense subgraphs

2007-02-05

arxiv.org/abs/cs/0702032v1

Computer Science

Data Structures and Algorithms

12 pages, no figures

Scientific paper

We consider two optimization problems related to finding dense subgraphs. The densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems are related to the well-known densest k-subgraph problem (DkS), which is to find the densest subgraph on exactly k vertices. We show that DalkS can be approximated efficiently, while DamkS is nearly as hard to approximate as the densest k-subgraph problem.

Affiliated with

Also associated with

No associations

Rating

Finding large and small dense subgraphs 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 Finding large and small dense subgraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding large and small dense subgraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-714250