Fixed Parameter Algorithms

In the context of fixed parameter algorithms, which was recently introduced by Downey and Fellows, it would be interesting to design an algorithm with running time $O(f(k) \vert V\vert^c)$ where $k$ is the size of the maximum clique, $c$ is a small constant independent of $k$ and $f(k)$ is a (exponential) function of $k$. Such an algorithm can work for small $k$ even for large $n$.

Contributed by Mohammad Taghi Hajiaghayi

Back to the main index for Perfect Graphs.