EN|RU

Volume 20, No 3, 2013, P. 26-44

UDC 519.178
Malyshev D. S. 
Ñlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable

Abstract:
Polynomial-time solvability of the independent set problem for some subclasses of subcubic planar graphs is proved.
Bibliogr. 5.

Keywords: independent set problem, boundary class, computational complexity, effective algorithm.

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

 © Sobolev Institute of Mathematics, 2015