Geodesic
Классы планарных графов с полиномиально разрешимой задачей о независимом множестве
Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 1, pp. 3-10 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

@article{DA_2008_15_1_a0,
     author = {V. E. Alekseev and D. S. Malyshev},
     title = {{\CYRK}{\cyrl}{\cyra}{\cyrs}{\cyrs}{\cyrery} {\cyrp}{\cyrl}{\cyra}{\cyrn}{\cyra}{\cyrr}{\cyrn}{\cyrery}{\cyrh} {\cyrg}{\cyrr}{\cyra}{\cyrf}{\cyro}{\cyrv} {\cyrs}~{\cyrp}{\cyro}{\cyrl}{\cyri}{\cyrn}{\cyro}{\cyrm}{\cyri}{\cyra}{\cyrl}{\cyrsftsn}{\cyrn}{\cyro} {\cyrr}{\cyra}{\cyrz}{\cyrr}{\cyre}{\cyrsh}{\cyri}{\cyrm}{\cyro}{\cyrishrt} {\cyrz}{\cyra}{\cyrd}{\cyra}{\cyrch}{\cyre}{\cyrishrt} {\cyro}~{\cyrn}{\cyre}{\cyrz}{\cyra}{\cyrv}{\cyri}{\cyrs}{\cyri}{\cyrm}{\cyro}{\cyrm} {\cyrm}{\cyrn}{\cyro}{\cyrzh}{\cyre}{\cyrs}{\cyrt}{\cyrv}{\cyre}},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--10},
     year = {2008},
     volume = {15},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2008_15_1_a0/}
}
TY  - JOUR
AU  - V. E. Alekseev
AU  - D. S. Malyshev
TI  - Классы планарных графов с полиномиально разрешимой задачей о независимом множестве
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2008
SP  - 3
EP  - 10
VL  - 15
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DA_2008_15_1_a0/
LA  - ru
ID  - DA_2008_15_1_a0
ER  - 
%0 Journal Article
%A V. E. Alekseev
%A D. S. Malyshev
%T Классы планарных графов с полиномиально разрешимой задачей о независимом множестве
%J Diskretnyj analiz i issledovanie operacij
%D 2008
%P 3-10
%V 15
%N 1
%U http://geodesic.mathdoc.fr/item/DA_2008_15_1_a0/
%G ru
%F DA_2008_15_1_a0
V. E. Alekseev; D. S. Malyshev. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве. Diskretnyj analiz i issledovanie operacij, Tome 15 (2008) no. 1, pp. 3-10. http://geodesic.mathdoc.fr/item/DA_2008_15_1_a0/

[1] Alekseev V. E., “O szhimaemykh grafakh”, Problemy kibernetiki, Vyp. 36, Nauka, M., 1979, 23–31 | MR

[2] Alekseev V. E., “O vliyanii lokalnykh ogranichenii na slozhnost opredeleniya chisla nezavisimosti grafa”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, Gorkovskii gos. un-t, Gorkii, 1983, 3–13 | MR

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

[4] Bodlaender H. L., “Dynamic programming on graphs with bounded treewidth”, Automata, languages and programming, Proc. (Tampere, 1988), Lecture Notes in Comput. Sci., 317, Springer, Berlin, 1988, 105–118 | MR

[5] Lozin V., Milanic M., “A polynomial algorithm to find an independent set of maximum weight in fork-free graphs”, Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms

[6] Robertson N., Seymour P., “Graph minors. III. Planar tree-width”, J. Combin. Theory. Ser. B, 36:1 (1984), 49–64 | DOI | MR | Zbl