D. S. Malyshev, V. E. Alekseev, “Boundary classes for the list-ranking problems in subclasses of forests”, Diskretn. Anal. Issled. Oper., 2011, Volume 18, Issue 6,Pages <nobr>61

This article is cited in 5 papers

Boundary classes for the list-ranking problems in subclasses of forests

D. S. Malyshev^a, V. E. Alekseev^b

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

Abstract: All boundary classes are found for the graph list-ranking problems (vertex and edge variants) relative to the class of forests. It allows to determine the complexity status of these problems for any hereditary class defined by a finite set of forbidden subgraphs under the class of forests. Bibliogr. 9.

Keywords: computational complexity, boundary class, relative boundary class, list-ranking problem, forest.

UDC: 519.178

Received: 19.01.2011
Revised: 09.08.2011