RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2012 Volume 19, Issue 3, Pages 58–64 (Mi da690)

This article is cited in 1 paper

Effective solvability of the independent set problem in a class of graphs without induced path and cycle with five vertices and a big clique

D. S. Malyshevab

a Nizhniy Novgorod State University, Nizhniy Novgorod, Russia
b Nizhniy Novgorod Higher School of Economics, Nizhniy Novgorod, Russia

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.

UDC: 519.178

Received: 01.08.2011



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024