A constant approximation algorithm for the densest k-subgraph problem on chordal graphs |
| |
| Authors: | Maria Liazi Ioannis Milis |
| |
| Affiliation: | a Department of Informatics and Telecommunications, University of Athens, 157 84 Athens, Greece
b Department of Informatics, Athens University of Economics and Business, 104 34 Athens, Greece |
| |
| 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. |
| |
| Keywords: | Densest k-subgraph Chordal graphs Approximation algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
