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
