Title: Densest $k$-Subgraph Approximation on Interval Graphs, Chordal Graphs and Planar Graphs
Speaker:  LI Jian
Fudan University

Date: Friday, March 23,2007
Time 11-12PM
Venue: Room  2578, HKUST

  
Abstract:
In this paper, we consider the densest $k$-subgraph problem on
interval graphs,  chordal graphs and planar graphs.
It is NP-hard on chordal graphs and planar graphs.
We give the first polynomial time approximation scheme for the 
densest $k$-subgraph problem on proper interval graphs and 
planar graphs, and a constant approximation algorithm on chordal graphs.