Geodesic
NP-Completeness of the~Dictionary Generation Problem
Matematičeskie trudy, Tome 9 (2006) no. 1, pp. 117-129

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

We prove that the Dictionary Generation Problem is NP-complete and consider the parametrized complexity of this problem. 
@article{MT_2006_9_1_a5,
     author = {V. Yu. Popov},
     title = {NP-Completeness of {the~Dictionary} {Generation} {Problem}},
     journal = {Matemati\v{c}eskie trudy},
     pages = {117--129},
     publisher = {mathdoc},
     volume = {9},
     number = {1},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/}
}
TY  - JOUR
AU  - V. Yu. Popov
TI  - NP-Completeness of the~Dictionary Generation Problem
JO  - Matematičeskie trudy
PY  - 2006
SP  - 117
EP  - 129
VL  - 9
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/
LA  - ru
ID  - MT_2006_9_1_a5
ER  - 
%0 Journal Article
%A V. Yu. Popov
%T NP-Completeness of the~Dictionary Generation Problem
%J Matematičeskie trudy
%D 2006
%P 117-129
%V 9
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/
%G ru
%F MT_2006_9_1_a5
V. Yu. Popov. NP-Completeness of the~Dictionary Generation Problem. Matematičeskie trudy, Tome 9 (2006) no. 1, pp. 117-129. http://geodesic.mathdoc.fr/item/MT_2006_9_1_a5/