Geodesic
The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 74-96.

Voir la notice de l'article provenant de la source Math-Net.Ru

We completely characterize all hereditary classes defined by at most three forbidden induced subgraphs (obstructions) for which the edge list-ranking problem is polynomial-time solvable. For each class in this family, the algorithm of determining the complexity status of the problem in the class is based on checking whether or not the obstructions belong to some special (“critical”) classes of graphs. The family of such special classes includes, in particular, inclusionwise minimal classes for which the problem is NP-complete. All classes of this type defined by at most three obstructions are described. Ill. 4, bibliogr. 14.
Keywords: computational complexity, minimal hard class, boundary class, edge list-ranking problem
Mots-clés : polynomial algorithm. 
@article{DA_2012_19_1_a5,
     author = {D. S. Malyshev},
     title = {The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {74--96},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2012_19_1_a5/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2012
SP  - 74
EP  - 96
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2012_19_1_a5/
LA  - ru
ID  - DA_2012_19_1_a5
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions
%J Diskretnyj analiz i issledovanie operacij
%D 2012
%P 74-96
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2012_19_1_a5/
%G ru
%F DA_2012_19_1_a5
D. S. Malyshev. The complexity analysis of the edge-ranking problem for hereditary graph classes with at most three prohibitions. Diskretnyj analiz i issledovanie operacij, Tome 19 (2012) no. 1, pp. 74-96. http://geodesic.mathdoc.fr/item/DA_2012_19_1_a5/

[1] Alekseev V. E., Malyshev D. S., “Kriterii granichnosti i ego primeneniya”, Diskret. analiz i issled. operatsii, 15:6 (2008), 3–10 | MR

[2] Korobitsyn D. V., “O slozhnosti opredeleniya chisla dominirovaniya v monogennykh klassakh grafov”, Diskret. matematika, 2:3 (1990), 90–96 | MR | Zbl

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

[4] Malyshev D. S., “O minimalnykh slozhnykh elementakh reshetki nasledstvennykh klassov grafov”, Mat. VII molodëzh. nauchn. shkoly po diskretnoi matematike i eë prilozheniyam (Moskva, 18–23 maya 2009 g.), chast II, Izd-vo IPM RAN, M., 2009, 12–17

[5] Malyshev D. S., Issledovanie granits effektivnoi razreshimosti v semeistve nasledstvennykh klassov grafov, Dis. $\dots$ kand. fiz.-mat. nauk, Nizhegorodskii gos. un-t, Nizhnii Novgorod, 2009, 113 pp.

[6] Malyshev D. S., “Posledovatelnye minimumy reshëtki nasledstvennykh klassov grafov dlya zadachi o rëbernom spiskovom ranzhirovanii”, Vestn. Nizhegorodskogo un-ta im. N. I. Lobachevskogo, 4:1 (2010), 133–136

[7] Malyshev D. S., “Minimalnye slozhnye klassy grafov dlya zadachi o rëbernom spiskovom ranzhirovanii”, Diskret. analiz i issled. operatsii, 18:1 (2011), 70–76 | MR

[8] Malyshev D. S., Alekseev V. E., “Granichnye klassy dlya zadach o spiskovom ranzhirovanii otnositelno lesov”, Diskret. analiz i issled. operatsii, 18:6 (2011), 61–70

[9] Alekseev V. E., “On easy and hard hereditary classes of graphs with respect to the independent set problem”, Discrete Appl. Math., 132 (2004), 17–26 | DOI | MR

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

[11] Ding G., “Subgraphs and well-quasi-ordering”, J. Graph Theory, 16 (1992), 489–502 | DOI | MR | Zbl

[12] Distel R., Graph Theory, Springer-Verl., New York, 2000, 322 pp. | MR

[13] Kral D., Kratochvil J., Tuza T., Woeginger G., “Complexity of coloring of graphs without forbidden induced subgraphs”, Graph-theoretic concepts in computer science, Proc. 27th Int. Workshop (Boltenhagen, Germany, June 14–16, 2001), Lect. Notes Comput. Sci., 2204, Springer-Verl., Berlin–Heidelberg, 2001, 254–262 | MR | Zbl

[14] Lozin V. V., “A decidability results for the dominating set problem”, Theor. Comput. Sci., 411:44–46, October (2010), 4023–4027 | DOI | MR