EN|RU

Volume 18, No 6, 2011, P. 61-70

UDC 519.178
D. S. Malyshev, V. E. Alekseev
Boundary classes for the list-ranking problems in subclasses of forests

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.

Malyshev Dmitrii Sergeevich 1
Alekseev Vladimir Evgen’evich 2

1. Nizhniy Novgorod Higher School of Economics,
25/12 B. Pecherskaya str., 603155 Nizhny Novgorod
2. Nizhniy Novgorod State University,
23 Gagarina ave., 603950 Nizhniy Novgorod, Russia
e-mail: dsmalyshev@rambler.ru, aleve@rambler.ru

 © Sobolev Institute of Mathematics, 2015