Constant factor approximation algorithms for the densest k-subgraph problem on proper interval graphs and bipartite permutation graphs |
| |
Authors: | Jonathan Backer |
| |
Affiliation: | University of Saskatchewan, Department of Computer Science, 176 Thorvaldson Building, 110 Science Place, Saskatoon, SK, Canada, S7N 5C9 |
| |
Abstract: | The densest k-subgraph problem asks for a k-vertex subgraph with the maximum number of edges. This problem is NP-hard on bipartite graphs, chordal graphs, and planar graphs. A 3-approximation algorithm is known for chordal graphs. We present -approximation algorithms for proper interval graphs and bipartite permutation graphs. The latter result relies on a new characterisation of bipartite permutation graphs which may be of independent interest. |
| |
Keywords: | Densest subgraph Proper interval graph Bipartite permutation graph Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|