Volume 20, No 3, 2013, P. 26-44
Malyshev D. S.
Đlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable
Polynomial-time solvability of the independent set problem for some subclasses of subcubic planar graphs is proved.
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
Nizhniy Novgorod State University,
23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia