Volume 19, No 3, 2012, P. 5864
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
email: dsmalyshev@rambler.ru
