YANG Yu-xing, WANG Shi-ying. A DNA Sticker Algorithm for the Ménage Problem[J]. Acta Electronica Sinica, 2012, 40(4): 751-755. DOI: 10.3969/j.issn.0372-2112.2012.04.021.
The traditional trend of DNA computing aims at solving computationally intractable problems in the filed of graph theory and permutation and combination.For the objective to solve the Ménage problem with biological operations
this paper gave a mathematical model and analyzed the difficulties of solving the problem with DNA computation.An improved mathematical model of the Ménage Problem to overcome these difficulties was proposed.In order to improve the efficiency
using the extended separation and extended multi-separation operation
this paper proposed a sticker DNA algorithm of the Ménage problem and analyzed the complexity of the algorithm.Consequently
it showed the operation steps and carried out simulation experiments by an instance.