NP-Completeness of the Dictionary Generation Problem

V. Yu. Popov

Ural State University

Abstract: We prove that the Dictionary Generation Problem is NP-complete and consider the parametrized complexity of this problem.

Key words: dictionary generation, NP-completeness, parametrized complexity.

UDC: 512+519.4

Received: 30.11.2004

 English version: Siberian Advances in Mathematics, 2006, 16:3, 115–125

Bibliographic databases:

•