Geodesic
The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
Diskretnaya Matematika, Tome 25 (2013) no. 2, pp. 63-67 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

@article{DM_2013_25_2_a5,
     author = {D. S. Malyshev},
     title = {The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem},
     journal = {Diskretnaya Matematika},
     pages = {63--67},
     year = {2013},
     volume = {25},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2013_25_2_a5/}
}
TY  - JOUR
AU  - D. S. Malyshev
TI  - The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
JO  - Diskretnaya Matematika
PY  - 2013
SP  - 63
EP  - 67
VL  - 25
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2013_25_2_a5/
LA  - ru
ID  - DM_2013_25_2_a5
ER  - 
%0 Journal Article
%A D. S. Malyshev
%T The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem
%J Diskretnaya Matematika
%D 2013
%P 63-67
%V 25
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2013_25_2_a5/
%G ru
%F DM_2013_25_2_a5
D. S. Malyshev. The impact of the growth rate of the packing number of graphs on the computational complexity of the independent set problem. Diskretnaya Matematika, Tome 25 (2013) no. 2, pp. 63-67. http://geodesic.mathdoc.fr/item/DM_2013_25_2_a5/

[1] Korobitsyn D. V., “O slozhnosti zadach na nasledstvennykh klassakh grafov”, Diskretnaya matematika, 4:4 (1992), 34–40 | MR | Zbl

[2] Malyshev D. S., “Sovmestnoe vliyanie kolichestva reber i komponent svyaznosti v grafakh na slozhnost vychisleniya chisla nezavisimosti”, Materialy Rossiiskoi konferentsii “Diskretnaya optimizatsiya i issledovanie operatsii”, IM SO RAN, Novosibirsk, 2010, 136

[3] Malyshev D. S., “Analiz vliyaniya chisla reber v svyaznykh grafakh na trudoemkost resheniya zadachi o nezavisimom mnozhestve”, Diskretnyi analiz i issledovanie operatsii, 18:3 (2011), 84–88 | MR | Zbl

[4] Chen J., Huang X., Kanj I., Xia G., “Strong computational lower bounds via parameterized complexity”, J. Computer and System Sci., 72 (2006), 1346–1367 | DOI | MR | Zbl

[5] Dantsin E., Wolpert A., “On moderately exponential time for SAT”, Lect. Notes Comput. Sci., 6175, 2010, 313–325 | DOI | Zbl

[6] Downey R., Fellows M., Parameterized complexity, Springer-Verlag, New York, 1999 | MR | Zbl

[7] Flum J., Grohe M., “Subexponential fixed-parameter tractability”, Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer-Verlag, 2006, 417–451

[8] Impagliazzo R., Paturi R., Zane F., “Which problems have strongly exponentional complexity?”, J. Computer and System Sci., 62 (2001), 512–530 | DOI | MR