We use cookies to improve your experience with our site.
Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang, Dong-Bo Bu, Ming Li. A Note on the Single Genotype Resolution Problem[J]. Journal of Computer Science and Technology, 2004, 19(2).
Citation:
Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang, Dong-Bo Bu, Ming Li. A Note on the Single Genotype Resolution Problem[J]. Journal of Computer Science and Technology, 2004, 19(2).
Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang, Dong-Bo Bu, Ming Li. A Note on the Single Genotype Resolution Problem[J]. Journal of Computer Science and Technology, 2004, 19(2).
Citation:
Hao Lin, Ze-Feng Zhang, Qiang-Feng Zhang, Dong-Bo Bu, Ming Li. A Note on the Single Genotype Resolution Problem[J]. Journal of Computer Science and Technology, 2004, 19(2).
This note settles the complexity of the single genotype resolution problem showing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R. Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardness of Maximum Resolution problem.
DownLoad: