Geodesic
Minimal hard classes of graphs for the edge list-ranking problem
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 70-76 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider the notion of a minimal hard class of graphs for the edge list-ranking 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. 
@article{DA_2011_18_1_a6,
     author = {D. S. Malyshev},
     title = {Minimal hard classes of graphs for the edge list-ranking problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {70--76},
     year = {2011},
     volume = {18},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_1_a6/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - Minimal hard classes of graphs for the edge list-ranking problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 70
EP  - 76
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_1_a6/
LA  - ru
ID  - DA_2011_18_1_a6
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T Minimal hard classes of graphs for the edge list-ranking problem
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 70-76
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2011_18_1_a6/
%G ru
%F DA_2011_18_1_a6
D. S. Malyshev. Minimal hard classes of graphs for the edge list-ranking problem. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 70-76. http://geodesic.mathdoc.fr/item/DA_2011_18_1_a6/

[1] Malyshev D. S., “O minimalnykh slozhnykh elementakh reshëtki nasledstvennykh klassov grafov”, Materialy VII molodëzh. nauch. shk. po diskret. matematike i eë pril., Chast II (Moskva, 18–23 maya 2009 g.), IPM RAN, M., 2009, 12–17

[2] Malyshev D. S., “O minimalnykh slozhnykh klassakh grafov”, Diskret. analiz i issled. operatsii, 16:6 (2009), 43–51 | MR

[3] Malyshev D. S., “Posledovatelnye minimumy reshetki nasledstvennykh klassov grafov dlya zadachi o rëbernom spiskovom ranzhirovanii”, Vestn. Nizhegorodsk. un-ta, 2010, no. 5, 125–130

[4] Bollobas B., Extremal graph theory, Academic Press, London, 1978, 488 pp. | MR | Zbl

[5] Dereniowski D., “The complexity of list ranking of trees”, Ars Combinatoria, 86 (2008), 97–114 | MR | Zbl