Volume 18, No 1, 2011, P. 70-76
D. S. Malyshev
Minimal hard classes of graphs for the edge list-ranking problem
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
Nizhniy Novgorod branch of Higher School of Economics,
25/12 B. Pecherskaya str., 603155 Nizhny Novgorod, Russia