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
