Volume 19, No 3, 2012, P. 58-64

UDC 519.178
D. S. Malyshev
Effective solvability of the independent set problem in a class of graphs without induced path and cycle with five vertices and a big clique

Abstract:
An algorithm for finding the independence number of a $n$-vertex graph from the class $\operatorname{Free}(\{P_5,C_5,K_p\})$ in time $O(n^{p+O(1)})$ is proposed.
Bibliogr. 10.

Keywords: the independent set problem, computational complexity, polynomial algorithm.

Malyshev Dmitrii Sergeevich ^1,2
1. Nizhniy Novgorod Higher School of Economics,
25/12 B. Pecherskaya str., 603155 Nizhny Novgorod, Russia
2. Nizhniy Novgorod State University,
23 Gagarina ave., 603950 Nizhniy Novgorod, Russia
e-mail: dsmalyshev@rambler.ru