The Dense k ‐Subgraph Problem

The Dense k ‐Subgraph Problem

0.00 Avg rating—0 Votes
Article ID: iaor20121012
Volume: 29
Issue: 3
Start Page Number: 410
End Page Number: 421
Publication Date: Mar 2001
Journal: Algorithmica
Authors: , ,
Keywords: graphical methods
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 .

Reviews

Required fields are marked *. Your email address will not be published.