D. S. Malyshev, “Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable”, Diskretn. Anal. Issled. Oper., 2013, Volume 20, Issue 3,Pages <nobr>26

This article is cited in 12 papers

Сlasses of subcubic planar graphs for which the independent set problem is polynomial-time solvable

D. S. Malyshev^ab

^a Nizhniy Novgorod Higher School of Economics, 25/12 B. Pecherskaya St., 603155 Nizhny Novgorod, Russia
^b Nizhniy Novgorod State University, 23 Gagarin Ave., 603950 Nizhniy Novgorod, Russia

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.

UDC: 519.178

Received: 10.11.2011
Revised: 19.11.2012