Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428155 | Information Processing Letters | 2008 | 4 Pages |
Abstract
The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics