Volume 18, No 1, 2011, P. 70-76

UDC 519.178
D. S. Malyshev
Minimal hard classes of graphs for the edge list-ranking problem

Abstract:
We consider the notion of a minimal hard class of graphs for the edge listranking problem. We investigate the way of obtaining such classes and reveal a new class of this kind. We show completeness of a set of some classes of graphs as a system of minimal hard classes that can be obtained in the framework of the proposed approach. Bibliogr. 5.

Keywords: computational complexity, minimal hard class, edge list-ranking problem.

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