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.
All Science Journal Classification (ASJC) codes
- Applied Mathematics
- Computer Science(all)
- Computer Science Applications
- Approximation algorithms
- Dense subgraph