 |
AUTHOR: Liazi Maria
TITLE: Approximation schemes, Colors & Densest subgraphs
RESEARCH AREAS:
- Algorithmic Operations Research
ADVISORY COMMITTEE:
- Supervisor: Zissimopoulos Vassilios
- Advisor: Elias Koutsoupias
- Advisor: Ioannis Milis
DESCRIPTION:
It is studied the problem of finding the Densest k-subgraph of a given graph. (DkS). The densest k-subgraph problem has very interesting applications. Indicatively we mention its application on the Web graph and on the random generation of test instances with controlled attributes. The research includes the development of polynomial algorithms for special graphs (trees, interval graphs…) and the development of approximation algorithms with guaranteed performance for general graphs. At the same time, because of the association of the problem with the clique problem and the coloring problem, the different versions of these problems are studied. Furthermore, the on-line version of the problem is a basic aim for the development and the analysis of algorithms with guaranteed competitive ratio.
|
![]](../images/rdcorner.gif){kind=small}